Original title: Generování jednoduchých nakreslení grafů
Translated title: Generating simple drawings of graphs
Authors: Čermák, Filip ; Balko, Martin (advisor) ; Valtr, Pavel (referee)
Document type: Bachelor's theses
Year: 2021
Language: eng
Abstract: [eng] [cze]
In this thesis, we study the crossing numbers of complete graphs. After introducing a long history of the old problem of determining the crossing number of Kn, we survey the recent progress on the Harary-Hill conjecture by compiling proofs of this conjecture for special classes of drawings of Kn. We also create a program for generating a database of all simple drawings of Kn with n ≤ 8. We implement another program that visualizes these drawings and allows the user to create its own simple drawings of general graphs. The visualizer also captures the structure of crossings of the displayed drawings. We use our programs to verify a conjecture by Balko, Fulek, and Kynčl for small cases and we find a mistake in a paper by Mutzel and Oettershagen. 1 V této práci se zabýváme průsečíkovými čísly úplných grafů. Nejprve uvedeme dlouhou historii velmi starého problému týkajícího se určení průsečíkového čísla Kn a poté ukážeme současný pokrok v Hararyho-Hillově domněnce postupným procházením jejích důkazů pro speciální třídy nakreslení Kn. Vytvoříme program pro generování databáze všech jednoduchých nakreslení Kn, kde n ≤ 8. Rovněž implementujeme program vizualizující tato nakreslení a umožňující uživateli vytvořit vlastní jednoduchá nakreslení obecných grafů. Vizualizér navíc zachycuje strukturu průsečíků zobrazených nakreslení. Naše pro- gramy využijeme k ověření domněnky Balka, Fulka a Kynčla pro malé případy a odhalíme chybu v článku autorů Mutzela a Oettershagena. 1
Keywords: crossing number|complete graph|k-edges|cumulated k-edges|the Harary--Hill conjecture; průsečíkové číslo|úplný graf|k-hrany|kumulované k-hrany|Hararyho--Hillova domněnka

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

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


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