Combinatorial structure of graph drawings

Abstract

In this thesis, we study characterization by forbidden patterns of many classes of x-monotone drawings of complete graphs with various given restrictions. We generalize previously known characterizations of pseudolinear, semisimple, and simple drawings of Kn by showing that also bounded pseudoparabola drawings of Kn can be characterized by finite forbidden patterns. On the other hand, we show that there is no such finite characterization for extended pseudoparabola drawings of Kn. We strengthen our results even further to so-called (da, di)-degree drawings where integers da and di represent a number of crossings between adjacent and independent edges, respectively. We provide a full characterization by forbidden patterns of each class of (da, di)-degree drawings. 1

V této práci se zabýváme charakterizací pomocí zakázaných vzorů mnoha tříd x- monotónních nakreslení úplných grafů s různými omezeními. Zobecňujeme dříve známé charakterizace pseudolineárních, polojednoduchých a jednoduchých nakreslení Kn tak, že ukazujeme, že i ohraničené pseudoparabolické kresby Kn mohou být charakterizovány konečnými zakázanými vzory. Na druhou stranu ukazujeme, že u rozšířených pseu- doparabolických nakreslení Kn žádná taková konečná charakterizace neexistuje. Naše výsledky ještě zesílíme na takzvané (da, di)-stupňové nakreslení, kde celá čísla da a di představují počet povolených křížení mezi sousedními, respektive nezávislými hranami. Poskytujeme také plnou charakterizaci pomocí zakázaných vzorů každé třídy (da, di)- stupňových nakreslení. 1