On Plane Straight-Line Graphs

B. Vogtenhuber

Abstract:

Geometric Graph Theory is a branch of both, Computational Geometry and Graph Theory, which deals with properties of straight-line embeddings of graphs as well as algorithmic issues. In this diploma thesis, we consider three topics within the area of plane geometric graphs, namely angle-constrained graphs, graph enumeration with Gray codes, and counting of graphs. The obtained results include (1) tight angle bounds for the openness of certain classes of angle-constrained graphs, thereby generalizing the concept of pointed pseudo-triangulations; (2) Gray codes for enumerating plane spanning trees, connected plane graphs, and all plane graphs in an efficient way; (3) lower and upper bounds for the asymptotically minimal and maximal numbers of certain types of geometric graphs. Results obtained during the work of this thesis have already been presented at international conferences and will appear as refereed journal articles.

Reference: B. Vogtenhuber. On plane straight-line graphs. Master's thesis, IST-TU Graz, Austria, January 2007. Supervisor: Oswin Aichholzer.