Original title: Kreslení grafů: Vizualizace a geometrické reprezentace grafů a sítí
Translated title: Graph Drawing: Visualisation and Geometric Representations of Graphs and Networks
Authors: Vyskočil, Tomáš ; Kratochvíl, Jan (advisor) ; Felsner, Stefan (referee) ; Kaiser, Tomáš (referee)
Document type: Doctoral theses
Year: 2015
Language: eng
Abstract: [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

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/82604

Permalink: http://www.nusl.cz/ntk/nusl-499460


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses