Hamiltonicity of maximal planar graphs and planar triangulations

Helden, Guido; Guo, Yubao

doi:urn:nbn:de:hbz:82-opus-19494

Hamiltonicity of maximal planar graphs and planar triangulations = Hamiltonkreise in maximal planaren Graphen und planaren Triangulationen

Helden, Guido (Author)

2007

Verantwortlichkeitsangabevorgelegt von Guido Helden

ImpressumAachen : Publikationsserver der RWTH Aachen University 2007

UmfangV, 102 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2007

Errata vom 21.05.2013

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Guo, Yubao (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2007-06-26

Online
URN: urn:nbn:de:hbz:82-opus-19494
URL: http://publications.rwth-aachen.de/record/62349/files/1949.pdf
URL: http://publications.rwth-aachen.de/record/62349/files/1949_Errata.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Hamilton-Kreis (Genormte SW) ; Graphentheorie (Genormte SW) ; Mathematik (frei) ; Maximal planarer Graph (frei) ; planare Triangulation (frei) ; Maximal planar graph (frei) ; planar triangulation (frei) ; separating triangle (frei) ; hamiltonian cycle (frei)

Thematische Einordnung (Klassifikation)
DDC: 510
msc: 05C10 * 05C45

Kurzfassung
Die vorliegende Arbeit untersucht die Existenz von Hamiltonkreisen und Hamiltonwegen in maximal planaren Graphen und planaren Triangulationen. Der erste Teil der Arbeit beschäftigt sich mit der Fragestellung, wie groß ist die maximale Zahl k, so dass jeder maximal planare Graph mit höchstens k trennenden Dreiecken hamiltonsch ist? Darüber hinaus liefert eine Strukturanalyse eine spezielle Struktur der Position der trennenden Dreiecke. Diese Struktur garantiert ebenfalls Hamiltonkreise. Des weiteren wird untersucht, wie viele Ecken eines hamiltonschen maximal planaren Graphen entfernt werden können, so dass der restliche Graph noch hamiltonsch ist. Der zweite Teil dieser Arbeit untersucht die Existenz von Hamiltonkreisen in planaren Triangulationen. Abschliessend werden in der Arbeit einigen Anwendungen von hamiltonschen maximal planaren Graphen und planaren Triangulationen in der Computergrafik und in der Chemie betrachtet.

This thesis mainly deals with the existence of hamiltonian cycles and hamiltonian paths in maximal planar graphs and planar triangulations. The first part of this dissertation focus on the question, what is the maximal number k, so that every maximal planar graph with at most k separating triangles is hamiltonian? An analysis of the structure shows a special structure of the position of the separating triangles to each other, which will also generate hamiltonicity. Moreover, this part deals with the question how many vertices of a hamiltonian maximal planar graph can be deleted, so that the remaining graph is still hamiltonian. The second part examines the existence of hamiltonian cycles in planar triangulations. This dissertation closes with some applications of hamiltonian maximal planar graphs and planar triangulations in computer graphics and chemistry.

Fulltext:
PDF
PDF