|
|
Graph Drawing: Visualisation and Geometric Representations of Graphs and Networks
Vyskočil, Tomáš ; Kratochvíl, Jan (advisor) ; Felsner, Stefan (referee) ; Kaiser, Tomáš (referee)
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
|
|
| |
|
|
Extending Partial Representations of Graphs
Klavík, Pavel ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In this thesis, we study geometric intersection representations of graphs. For a fixed class, the well-known recognition problem asks whether a given graph belongs to this class. We study a generalization of this problem called partial representation extension. Its input consists of a graph with a partial representation, so a part of the graph is pre-drawn. The problems asks whether this partial representation can be extended to a representation of the entire graph. We study this problem for classes of interval graphs, proper interval graphs, unit interval graphs and chordal graphs (in the setting of subtrees-in-tree representations). We give linear-time algorithms for the first two classes and an almost quadratic-time algorithm for unit interval graphs. For chordal graphs, we consider different versions of the problem and show that almost all cases are NP-complete. Even though the classes of proper and unit interval graphs are known to be equal, the partial representation extension problem distinguishes them. For unit interval graphs, it poses additional restrictions concerning precise positions of intervals, and we describe a new structure of unit interval representations to deal with this. 1
|
|
|
Representations and Visualization of Graphs
Štola, Jan ; Kratochvíl, Jan (advisor) ; Valtr, Pavel (referee) ; Wood, David (referee)
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.
|
|
|
Computational complexity in graph theory
Doucha, Martin ; Kratochvíl, Jan (advisor) ; Dvořák, Zdeněk (referee)
This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
|
|
|
Computational complexity in graph theory
Melka, Jakub ; Kratochvíl, Jan (advisor) ; Fiala, Jiří (referee)
In the present work we study the problem of reconstructing a graph from its closed neighbourhood list. We will explore this problem, formulated by V. Sós, from the point of view of the fixed parameter complexity. We study the graph reconstruction problem in a more general setting, when the reconstructed graph is required to belong to some special graph class. In the present work we prove that this general problem lies in the complexity class FPT, when parametrized by the treewidth and maximum degree of the reconstructed graph, or by the number of certain special induced subgraphs if the reconstructed graph is 2-degenerate. Also, we prove that the graph reconstruction problem lies in the complexity class XP when parametrized by the vertex cover number. Finally, we prove mutual independence of the results
|
|
|
Transmitted means of communication in history
Kratochvíl, Jan ; Smetáček, Vladimír (advisor) ; Machytka, Jan (referee)
Cílem této bakalářské práce je popsat vývoj vybraných přenosových prostředků komunikace v historii. Práci lze rozdělit na dvě části, ve kterých se postupně setkáváme s různými přenosovými prostředky. První se věnuje optickým telegrafním systémům od antiky přes pochodňové telegrafy do poloviny 17. stol. Druhá část je zaměřena na vyspělé telegrafy R. Hooka (1635-1703), C. Chappeho (1763-1805), A. N. Edelcrantze (1754-1821), G. Murraye (1761-1803). U přenosových prostředků je hlavně zkoumáno: dosah komunikace, její důvod, rychlost a utváření komunikačních sítí.
|
|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (advisor) ; Manlove, David (referee) ; Fiala, Jiří (referee)
Title: Computational Complexity in Graph Theory Author: Eva Jelínková Department: Department of Applied Mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., Department of Applied Mathematics Abstract: We address problems from graph theory, especially from the computational complexity point of view. In the first part of the thesis we address the computational complexity of problems related to Seidel's switch- ing of graphs. We prove that the problem to decide if a given graph can be switched to contain at most a given number of edges is NP-complete, even for graphs with bounded density. We thus partially answer a question of Matoušek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014]. We also describe infinitely many graphs H such that it is NP-complete to decide if a given graph is switching-equivalent to a graph that does not contain H as an induced subgraph. We thus close an open problem of Kratochvíl, Nešetřil and Zýka [Annals of Discrete Math. 51, 1992]. In the second part of the thesis we address the topic of matchings under preferences. We focus on the housing market problem, in particular, on the model with duplicate houses. We present a 2-approximation algorithm for the maximum number of satisfied agents when the preference lists of agents are trichotomic. On the other hand, we...
|
|
| |
|
|
Hry na grafech
Gavenčiak, Tomáš ; Kratochvíl, Jan (advisor) ; Pergel, Martin (referee)
In this thesis we study properties of one cop&robber game. In this game two players (Cop and Robber) take turns in moving on a finite undirected graph. Both players move with the speed at most one edge per turn. They both know the complete game status. If at any time Cop shares a vertex with Robber, Cop wins. If that never happens, Robber wins. Games of this type are important as models of searching in graphs and networks and for the connection to the width parameters of graphs. We closely examine the class of graphs with a winning strategy for Cop (the so called cop-win graphs) and construct best strategies for both Cop and Robber. The previously known results include the fact that the number of moves in which Cop can catch Robber on every cop-win graph on n vertices is bounded by n3 and there are graphs which require n 4. We show that this number is exactly n 4.
|
guest ::
RSS feed.