Název: Kreslení grafů: Vizualizace a geometrické reprezentace grafů a sítí
Překlad názvu: Graph Drawing: Visualisation and Geometric Representations of Graphs and Networks
Autoři: Vyskočil, Tomáš ; Kratochvíl, Jan (vedoucí práce) ; Felsner, Stefan (oponent) ; Kaiser, Tomáš (oponent)
Typ dokumentu: Disertační práce
Rok: 2015
Jazyk: eng
Abstrakt: [eng] [cze]
Title: Graph Drawing: Visualization and Geometric Representations of Graphs and Networks Author: Tomáš Vyskočil Department: Department of applied mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., KAM Abstract: This thesis is devoted to studying of representations of graphs. In Chapters 2-4 we study intersection graphs in the plane. In Chapter 5 we consider problems of modifications of graphs. Regarding intersection graphs, we prove that all complements of partial 2- trees are intersection graphs of segments. We show complexity of recognition of intersection graphs of path in the grid with bounded number of bends and intersection graphs of connected regions (we call them islands) in the extended grids. In the part devoted to modification problems we present a fixed-parameter tractable (FPT) algorithm which answers the question whether a given graph can be made planar with at most k contractions and we also provide gener- alization of this problem. Keywords: graph theory, graph representations, combinatorics Název práce: Kreslení grafů: Vizualizace a geometrické reprezentace grafů a sítí Autor: Tomáš Vyskočil Katedra: Katedra applikované matematiky Vedoucí: Prof. RNDr. Jan Kratochvíl, CSc., KAM Abstrakt: Tato práce se věnuje studiu reprezentací grafů. V kapitolách 2-4 studujeme průnikové grafy v rovině a v kapitole 5 studujeme problémy modi- fikací grafů pomocí jednoduchých operací. V části věnované průnikovým grafům se věnujeme následujícím. Ukážeme, že částečné 2-stromy jsou průnikové grafy úsečkových grafů. Dále ukážeme složitost rozpoznání průnikových grafů k lomených cest na mřížce a průnikových grafů ostrovů v rozšířené mřížce. V části věnované modifikacím grafů ukážeme FPT-algoritmus který řeší problém, zda můžeme získat rovinný graf ze vstupního grafu pomocí nejvýše k kontrahovaných hran a zobecnění tohoto problému. Klíčová slova: teorie grafů, reprezentace grafů, kombinatorika

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/82604

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-352246


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Disertační práce