velikost textu

Representations and Visualization of Graphs

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Representations and Visualization of Graphs
Název v češtině:
Reprezentace a vizualizace grafů
Název v angličtině:
Representations and visualization of graphs
Typ:
Disertační práce
Autor:
Mgr. Jan Štola, Ph.D.
Školitel:
prof. RNDr. Jan Kratochvíl, CSc.
Oponenti:
doc. RNDr. Pavel Valtr, Dr.
Prof. David Wood
Id práce:
42673
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
29. 7. 2010
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Abstract v angličtině:
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.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Jan Štola, Ph.D. 662 kB
Stáhnout Abstrakt v českém jazyce Mgr. Jan Štola, Ph.D. 80 kB
Stáhnout Abstrakt anglicky Mgr. Jan Štola, Ph.D. 80 kB
Stáhnout Posudek vedoucího prof. RNDr. Jan Kratochvíl, CSc. 52 kB
Stáhnout Posudek oponenta doc. RNDr. Pavel Valtr, Dr. 32 kB
Stáhnout Posudek oponenta Prof. David Wood 177 kB
Stáhnout Záznam o průběhu obhajoby 30 kB