Chromatic invariants in graph drawing
Chromatic invariants in graph drawing
diplomová práce (OBHÁJENO)
![Náhled dokumentu](/bitstream/handle/20.500.11956/3703/thumbnail.png?sequence=7&isAllowed=y)
Zobrazit/ otevřít
Trvalý odkaz
http://hdl.handle.net/20.500.11956/3703Identifikátory
SIS: 44054
Kolekce
- Kvalifikační práce [10925]
Autor
Vedoucí práce
Oponent práce
Valtr, Pavel
Fakulta / součást
Matematicko-fyzikální fakulta
Obor
Teoretická informatika
Katedra / ústav / klinika
Katedra aplikované matematiky
Datum obhajoby
22. 5. 2006
Nakladatel
Univerzita Karlova, Matematicko-fyzikální fakultaJazyk
Angličtina
Známka
Výborně
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)
This paper studies the question: What is the maximum integer kb,n such that every kb,n-colorable graph has a b-bend n-din1ensional orthogonal box drawing? We give an exact answer for the orthogonal line drawing in all dimensions and for the 3-dimensional rectangle visibility representation. We present an upper and lower bound for the 3-dimensional orthogonal drawing by rectangles and general boxes. Particularly, we improve the best known upper bound for the 3-dimensional orthogonal box drawing from 183 to 42 and the lower bound from 3 to 22. Powered by TCPDF (www.tcpdf.org)