velikost textu

Extension Properties of Graphs and Structures

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:
Extension Properties of Graphs and Structures
Název v češtině:
Rozšiřující vlastnosti grafů a struktur
Typ:
Disertační práce
Autor:
Mgr. Pavel Klavík
Školitel:
prof. RNDr. Jaroslav Nešetřil, DrSc.
Oponenti:
Jozef Širáň
prof. Pavol Hell
Id práce:
127605
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Informatický ústav Univerzity Karlovy (32-IUUK)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
12. 9. 2017
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Abstrakt:
Rozšiřovací vlastnosti grafů a struktur Pavel Klavík Hlavní motivace pro studium kreslení grafů a geometrických reprezentací je najít způ- soby, jak vizualizovat grafy efektivně, aby jejich struktura byla tak srozumitelná, jak je to jenom možné. V této práci se zaměřujeme na strukturální vlastnosti, které vyplývají z toho, že grafy mají určitý druh geometrických reprezentací. Studujeme dva druhy geo- metrických reprezentací: Průnikové reprezentace, ve kterých jsou vrcholy reprezentovány geometrickými množinami, zatímco hrany jsou kódovány jejich průniky, a rovinná vnoření rovinných grafů, což jsou kreslení grafů do roviny bez křížení hran. Z existence geomet- rické reprezentace lze vyvodit dodatečné informace o grafu. Hlavní myšlenka této práce je se ptát, jaká další informace se dá vyvodit ze struktury všech možných geometrických reprezentací. V části I studujeme problém rozšiřování částečných reprezentací pro průnikové reprezen- tace. Vedle grafu obsahuje vstup také částečnou reprezentaci, která předepisuje reprezentaci indukovaného podgrafu. Ptáme se, zdali je možné tuto částečnou reprezentaci rozšířit na plnou reprezentaci vstupního grafu, aniž bychom pozměnili předepsané množiny. Tento pro- blém jsem uvedl v roce 2010 ve své bakalářské práci. Popisujeme přehled známých výsledků pro řadu grafových tříd. Soustředíme se na intervalové grafy a dokazujeme jak strukturální, tak algoritmické výsledky pro jejich problém rozšiřování částečných reprezentací. V části II studujeme algebraické vlastnosti grafů, konkrétně jejich grupy automorfismů, problém grafového izomorfismu a regulární nakrytí grafů. Hlavní strukturální nástroj je 3-souvislá redukce, která rozkládá libovolný graf G na jeho 3-souvislé komponenty. Hlavně se soustředíme na rovinné grafy, ale řada našich výsledků funguje i pro obecné grafy. V roce 1867 popsal Jordan induktivní charakterizaci grup automorfismů stromů. My popi- sujeme první Jordanovskou induktivní charakterizaci grup automorfismů rovinných grafů. Také studujeme pro řadu grafových tříd a parametrů problém grafového izomorfismu ome- zeného seznamy. Pro regulární grafové nakrytí popisujeme všechny regulární kvocienty ro- vinných grafů a konstruujeme FPT algoritmus pro testování existence regulárního nakrytí pro rovinné vstupy. 1
Abstract v angličtině:
Extension Properties of Graphs and Structures Pavel Klavík The main motivation for graph drawing and geometric representations is finding ways to visualize graphs efficiently to make their structure as understandable as possible. In this thesis, we are concerned with structural properties which are implied for graphs having certain geometric representations. We study two types of geometric representations: inter- section representations in which the vertices are represented by geometric sets while the edges are encoded by their intersections, and planar embeddings of planar graphs which are drawing of graphs into the plane without crossing edges. The existence of geometric representations can be used to deduce additional information about graphs. The main idea of this thesis is to ask what extra information can be deduced from the structure of all possible geometric representations. In Part I, we study the partial representation extension problems for intersection rep- resentations. Aside from the graph, the input also gives a partial representation, which prescribes a representation of an induced subgraph. We ask whether this partial repre- sentation can be extended to a full representation of the input graph without altering the predrawn sets. I introduced this problem in 2010 in my Bachelor’s thesis. We sur- vey the state-of-the-art results for many graph classes. We concentrate on interval graphs and prove both structural and algorithmic results for the partial representation extension problem. In Part II, we study algebraic properties of graphs, namely their automorphism groups, the graph isomorphism problem and regular graph covering. The main structural tool is the 3-connected reduction which decomposes each graph G into 3-connected components. We are mostly concerned with planar graphs, but some of our results apply to general graphs. In 1867, Jordan described an inductive characterization of the automorphism groups of trees. We describe the first Jordan-like inductive characterization of the automorphism groups of planar graphs. Also, we study the list restricted graph isomorphism problem for variety of graph classes and parameters. For regular graph covering, we describe all regular quotients of planar graphs and construct an FPT algorithm for testing regular graph covering for planar inputs. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Pavel Klavík 5.77 MB
Stáhnout Abstrakt v českém jazyce Mgr. Pavel Klavík 74 kB
Stáhnout Abstrakt anglicky Mgr. Pavel Klavík 73 kB
Stáhnout Posudek vedoucího prof. RNDr. Jaroslav Nešetřil, DrSc. 46 kB
Stáhnout Posudek oponenta Jozef Širáň 277 kB
Stáhnout Posudek oponenta prof. Pavol Hell 40 kB
Stáhnout Záznam o průběhu obhajoby prof. RNDr. Martin Loebl, CSc. 153 kB