Hamiltonicity of maximal planar graphs and planar triangulations

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.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2007

Author dc:creator

• Helden, Guido

Contributors dc:contributor

• Guo, Yubao

• info:eu-repo/classification/ddc/510
• Hamilton-Kreis
• Graphentheorie
• Mathematik
• Maximal planarer Graph
• planare Triangulation
• Maximal planar graph
• planar triangulation
• separating triangle
• hamiltonian cycle

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-123920%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:62349