Hamiltonicity of maximal planar graphs and planar triangulations [Elektronische Ressource] / vorgelegt von Guido Helden

Hamiltonicity of maximal planar graphs andplanar triangulationsVon der Fakult at fur Mathematik, Informatik und Naturwissenschaftender Rheinisch-Westf alischen Technischen Hochschule Aachenzur Erlangung des akademischen Grades eines Doktors derNaturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-Mathematiker Guido Heldenaus AachenBerichter: Professor Dr. Yubao GuoUniversit atsprofessor Dr. Dr. h.c. Hubertus Th. JongenTag der mundlic hen Prufung: 26.06.2007Diese Dissertation ist auf den Internetseiten der Hochschulbibliothekonline verfugbar.PrefaceOne of the typical topics in graph theory is the study of planar graphs. Planar graphsarise quite naturally in real-world applications, such as road or railway maps and chemicalmolecules. The cartographers of the past were aware of the fact that any map on the planecould be colored with four or fewer colors so that no adjacent countries were colored alike.It was the Four Color Problem which stimulated interest in hamiltonian planar graphs. Agraph is said to be hamiltonian if it has a cycle that contains all vertices exactly once. Ifa planar graph is hamiltonian, then it is easy to color its faces with four or fewer colors sothat no two adjacent faces are colored alike. Moreover, planar graphs play an importantrole as some practical problems can be e cien tly solved for planar graphs even if they areintractable for general graphs.The study of planar graphs was initiated by L.