Bounded-degree graphs have arbitrarily large geometric thickness

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00002507" target="_blank" >RIV/00216208:11320/06:00002507 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Bounded-degree graphs have arbitrarily large geometric thickness
Original language description
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. We prove that there exists regular graphs of bounded degree with arbitrarily large geometric thickness. Analogous results concerning graph drawings with few edge slopes are also presented.
Czech name
Grafy omezeného stupně mají libovolně velkou geometrickou tloušťku
Czech description
Geometrická tloušťka grafu G je minimální číslo k takové, že existuje nakreslení G, v němž hrany jsou reprezentovány úsečkami a množinu hran lze rozdělit na k podmnožin tak, že každá z nich je nakreslena bez křížení. Dokazuje se, že existují regulární grafy stupně omezeného konstantou, pro něž je geometrická tloušťka libovolně velká. Podobné výsledky se dostanou pro nakreslení grafů, v nichž je omezen počet směrnic hran.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)