|
|
Representations and Visualization of Graphs
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent) ; Wood, David (oponent)
The 3D visibility (graph) drawing is a graph drawing in IR3 where vertices are represented by 2D sets placed into planes parallel to xy-plane and the edges correspond to z-parallel visibility among these sets. We continue the study of 3D visibility drawing of complete graphs by rectangles and regular polygons. We show that the maximum size of a complete graph with a 3D visibility drawing by regular n-gons is O(n4). This polynomial bound improves signifficantly the previous best known (exponential) bound 6n3 3n1 3 26n.We also provide several lower bounds. We show that the complete graph K2k+3 (resp. K4k+6) has a 3D visibility drawing by regular 2k-gons (resp.(2k + 1)-gons). We improve the best known upper bound on the size of a complete graph with a 3D visibility drawing by rectangles from 55 to 50. This result is based on the exploration of unimodal sequences of k-tuples of numbers. A sequence of numbers is unimodal if it rst increases and then decreases. A sequence of k-tuples of numbers is unimodal if it is unimodal in each component. We derive tight bounds on the maximum length of a sequence of k-tuples without a unimodal subsequence of length n. We show a connection between these results and Dedekind numbers, i.e., the numbers of antichains of a power set P(1; : : : ; k) ordered by inclusion.
|
|
|
Chromatic invariants in graph drawing
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent)
V této práci se zabýváme vlivem barevnosti grafu na existenci různých druhů ortogonálních nakreslení tohoto grafu. Studujeme otázku, jak velké můžeme volit kb,n tak, aby každý graf barevnosti nejvýše kb,n měl n-rozměrné ortogonální nakreslení s hranami s nejvýše b ohyby. kb,n nazývá1ne multipartitním číslem reprezentace/ nakreslení. Pro ortogonální nakreslení, v nichž jsou vrcholy reprezentovány úsečkami v IRn, je v práci multipartitní číslo odvozeno přesně pro všechna n. Přesná hodnota je určena taktéž pro viditelnostní reprezentace pomocí obdélníků a čtverců. Navíc jsou vylepšeny nejlepší známé horní a dolní odhady pro trojrozměrné ortogonální nakreslení pomocí obdélníků a hranolů. Dolní odhad je zvýšen ze 3 na 22 a horní snížen ze 183 na 42. Powered by TCPDF (www.tcpdf.org)
|
|
|
Representations and Visualization of Graphs
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent) ; Wood, David (oponent)
The 3D visibility (graph) drawing is a graph drawing in IR3 where vertices are represented by 2D sets placed into planes parallel to xy-plane and the edges correspond to z-parallel visibility among these sets. We continue the study of 3D visibility drawing of complete graphs by rectangles and regular polygons. We show that the maximum size of a complete graph with a 3D visibility drawing by regular n-gons is O(n4). This polynomial bound improves signifficantly the previous best known (exponential) bound 6n3 3n1 3 26n.We also provide several lower bounds. We show that the complete graph K2k+3 (resp. K4k+6) has a 3D visibility drawing by regular 2k-gons (resp.(2k + 1)-gons). We improve the best known upper bound on the size of a complete graph with a 3D visibility drawing by rectangles from 55 to 50. This result is based on the exploration of unimodal sequences of k-tuples of numbers. A sequence of numbers is unimodal if it rst increases and then decreases. A sequence of k-tuples of numbers is unimodal if it is unimodal in each component. We derive tight bounds on the maximum length of a sequence of k-tuples without a unimodal subsequence of length n. We show a connection between these results and Dedekind numbers, i.e., the numbers of antichains of a power set P(1; : : : ; k) ordered by inclusion.
|
|
|
Chromatic invariants in graph drawing
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent)
V této práci se zabýváme vlivem barevnosti grafu na existenci různých druhů ortogonálních nakreslení tohoto grafu. Studujeme otázku, jak velké můžeme volit kb,n tak, aby každý graf barevnosti nejvýše kb,n měl n-rozměrné ortogonální nakreslení s hranami s nejvýše b ohyby. kb,n nazývá1ne multipartitním číslem reprezentace/ nakreslení. Pro ortogonální nakreslení, v nichž jsou vrcholy reprezentovány úsečkami v IRn, je v práci multipartitní číslo odvozeno přesně pro všechna n. Přesná hodnota je určena taktéž pro viditelnostní reprezentace pomocí obdélníků a čtverců. Navíc jsou vylepšeny nejlepší známé horní a dolní odhady pro trojrozměrné ortogonální nakreslení pomocí obdélníků a hranolů. Dolní odhad je zvýšen ze 3 na 22 a horní snížen ze 183 na 42. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.