
Computational and structural apects of interval graphs and their variants
Novotná, Jana ; Kratochvíl, Jan (advisor) ; Jelínek, Vít (referee)
Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphsa generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semiclosed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not clawfree, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs. The original bubble model was used by Boyaci, Ekim, and Shalom for proving the polynomiality of the MaxCut problem on unit interval graphs. However, we found a significant mistake in the proof which seems to be hardly repairable. Moreover, we demonstrate advantages of such model by providing a subexponentialtime algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomialtime...


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)
