Original title: Kombinatorická struktura grafových nakreslení
Translated title: Combinatorial structure of graph drawings
Authors: Čermák, Filip ; Balko, Martin (advisor) ; Valtr, Pavel (referee)
Document type: Master’s theses
Year: 2024
Language: eng
Abstract: [eng] [cze]
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
Keywords: graph drawing|signotope|pseudolines|monotone curves; nakreslení grafu|signotopy|pseudopřímky|monotoní křivky

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/190917

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


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