Bakalářská práce

Case analysis of a splitter theorem

Matúš Hlaváčik
Anotace

Po mnoha letech výzkumu C. Chun, D. Mayhew a J. G. Oxley publikovali novou splitter theorem, kterou bychom mohli využít na algoritmus hledaní vnitřně 4-souvislých grafů, které mohou mít planární emulátory, za účelem omezení možných protipříkladů na Fellowsovu hypotézu o planárnych emulátoroch. V této práci vysvětlujeme vše potřebné pro pochopení této nové splitter theorem (obsahuje části teorii grafů …více

Abstract

After many years of research C. Chun, D. Mayhew, and J. G. Oxley published a new splitter theorem which we could use in an algorithm for finding internally 4-connected graphs which can have planar emulators. The purpose is to limit the possible counter-examples to Fellow's planar emulator conjecture. In this work, we explain everything needed for understanding this new splitter theorem (contains pieces …více

Klíčová slova
graph matroid finite planar cover finite planar emulator internally 4-connected two disjoint k-graphs splitter theorem
Zadání práce
The goal of the thesis is to analyse special graph cases of a very recent working preprint of Chun, Mayhew and Oxley about a new splitter theorem for internally 4-connected matroids. The student shall restrict his attention only to the cases in which the base minor in the theorem is a non-projective graph and the target graph does not contain two disjoint k-graphs. The expected outcome is a description of an algorithm (based on this splitter theorem) for generating all internally 4-connected graphs without two disjoint k-graphs, that extend a given internally 4-connected non-projective graph. This research is relevant to the open problem of characterizing planar-emulable graphs.
Administrativní informace
Práce zkontrolována:
25. 5. 2016 13:12, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
1,1 MB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
24. 6. 2016
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponent

RNDr. Jakub Gajarský, Ph.D., učo 172462
ITI FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.