
Průnikové reprezentace grafů
Töpfer, Martin ; Jelínek, Vít (advisor) ; Pangrác, Ondřej (referee)
This thesis is devoted to the outer and grounded string representations of graphs and their subclasses. A string representation of a graph is a set of strings (bounded continuous curves in a plane), where each string corresponds to one vertex of the graph. Two strings intersect each other if and only if the two corresponding vertices are adjacent in the original graph. An outer string graph is a graph with a string representation where strings are realized inside a disk and one endpoint of each string lies on the boundary of the disk. Similarly, in case of grounded string graphs the strings lie in a common half plane with one endpoint of each string on the boundary of the halfplane. We give a summary of subclasses of grounded string graphs and proves several results about their mutual inclusions and separations. To prove those, we use an orderforcing lemma which can be used to force a particular order of the endpoints of the string on the boundary circle or boundary line. The second part of the thesis contains proof that recognition of outer string graphs is NPhard. 1


The complexity of constrained graph drawing
Hora, Martin ; Jelínek, Vít (advisor) ; Fink, Jiří (referee)
A labeled embedding of a planar graph G is a pair (G, g) consisting of a planar drawing G of G and a function g assigning labels (colors) to the faces of G. We study the problem of Embedding Restriction Satisfiability (ERS) that investi gates whether a given graph has a labeled embedding satisfying a provided set of conditions. ERS is a relatively new problem, so not much is known about it. Nevertheless, it has great potential. It generalizes several problems looking for a particular drawing of a planar graph, such as the problem of Partially Embedded Planarity. Therefore, ERS may become a focal point in the area of graph draw ing. In this thesis, we examine the computational complexity of ERS. We show that ERS is NPcomplete. After that, we look at the complexity of some specific classes of its instances. We try to locate the boundary between the NPcomplete and the polynomial variants of the problem. 1


Enumeration of polyomino fillings
Karpilovskij, Mark ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
We prove two new results about 01fillings of skew diagrams avoiding long increasing and decreasing chains. In the first half of the thesis, we show that for a large class of skew diagrams, there is a bijection between sparse fillings avoiding an increasing chain of fixed length and sparse fillings avoiding a decreas ing chain of the same length. In the second half, we extend a known inequality between the number of sparse 01fillings of skew diagrams avoiding an increasing chain of length 2 and a decreasing chain of length 2 to all 01fillings. 1


Structural properties of hereditary permutation classes
Opler, Michal ; Jelínek, Vít (advisor) ; Valtr, Pavel (referee)
A permutation class C is splittable if it is contained in a merge of its two proper subclasses, and it is 1amalgamable if given two permutations σ, τ ∈ C, each with a marked element, we can find a permutation π ∈ C containing both σ and τ such that the two marked elements coincide. In this thesis, we study both 1amalgamability and splittability of permutation classes. It was previously shown that unsplittability implies 1amalgamability. We prove that unsplittability and 1amalgamability are not equivalent properties of permutation classes by showing that there is a permutation class that is both splittable and 1amalgamable. Moreover, we show that there are infinitely many such classes. Our construction is based on the concept of LRinflations or more generally on hereditary 2colorings, which we both introduce here and which may be of independent interest. 1


An algorithm for extending partial planar drawings
Hora, Martin ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
This thesis studies the problem of partially embedded planarity. The input of the problem is a graph G and a planar drawing of a subgraph of G. The goal is to decide whether the drawing of the subgraph can be extended to a planar drawing of the entire graph G. It has already been proved that the partially embedded planarity problem can be solved in linear time. However, all known linear algorithms are relatively complicated. This is probably the reason that no implementation has yet been published. We will introduce a new, simpler linear algorithm that solves the problem and we will prove its correctness. Next, we will enclose an implementation of this algorithm in the C++ programming language. 1


Hereditary classes of binary matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Klazar, Martin (referee)
Interval minors of binary matrices were introduced by Jacob Fox in the study of StanleyWilf limits. We study what can be implied from their relation to the theory of pattern avoidance of submatrices, which is a very popular area of discrete mathematics. We start by characterizing matrices avoiding small interval minors. We then consider classes of matrices closed under interval minors and we find classes of matrices that cannot be described by a finite number of forbidden interval minors. We also define and study a variant of a classical extremal Tur'an type question studied in the area of combinatorics of permutations and binary matrices and in combinatorial geometry. 1


Intersection representations of graphs
Töpfer, Martin ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
We investigate intersection graphs of axisaligned Lshapes (Lgraphs) and their subclass, when all L shapes have one of their endpoints on the same line  let us call this class outerLgraphs. In the beginning we introduce some known facts about Lgraphs. Then we show, that interval, circular and outerplanar graphs are subclasses of outerLgraphs. We also characterise outerLgraphs using ordering without forbidden patterns. Powered by TCPDF (www.tcpdf.org)


Generating random patternavoiding matrices
Kučera, Stanislav ; Jelínek, Vít (advisor) ; Šámal, Robert (referee)
Binary matrices not containing a smaller matrix as a submatrix have become an interesting topic recently. In my thesis, I introduce two new algorithms to test whether a big square binary matrix contains a smaller binary matrix together with a process using randomness, which approximates a uniformly random matrix not containing a given matrix. The reason to create such algorithms is to allow researchers test their conjectures on random matrices. Thus, my thesis also contains an effective cross platform implementation of all mentioned algorithms. Powered by TCPDF (www.tcpdf.org)


Structure and enumeration of permutation classes
Karpilovskij, Mark ; Jelínek, Vít (advisor) ; Balko, Martin (referee)
We define the operation of composing two hereditary classes of permutations using the standard composition of permutations as functions and we explore properties and structure of permutation classes considering this operation. We mostly concern ourselves with the problem of whether permutation classes can be composed from their proper subclasses. We provide examples of classes which can be composed from two proper subclasses, classes which can be composed from three but not from two proper subclasses and classes which cannot be composed from any finite number of proper subclasses. Powered by TCPDF (www.tcpdf.org)


Cops and robber game on directed complete graphs
Slívová, Veronika ; Gavenčiak, Tomáš (advisor) ; Jelínek, Vít (referee)
BACHELOR THESIS  ABSTRACT Veronika Slívová This thesis focuses on the game Cops and robber on tournaments (a graph we gain by orienting each edge of undirected complete graph). We show that tournaments containing a vertex with large outdegree have small cop number. On the other hand we prove that the number of cops we need to capture the robber on any tournament is not bounded. Then we study circulant tournaments and graphs obtained by cyclically orienting each triple of Steiner triple system. We disprove the conjecture made by Geňa Hahn that the cop number of any graph obtained by orientation Steiner triple system is bounded. We also show that the cop number of circulant tournaments cannot be bounded. Then we focus on the 2fast cop and the 2fast robber variant of the game. We prove that one 2fast cop wins on any tournament. On the contrary in case that the game is played on tournament whose vertices have the same outdegree, the 2fast robber is captured trivially or runs away indefinitely.
