Structural and enumerative problems for plane geometric graphs

• Autores: Clemens Huemer
• Directores de la Tesis: Oswin Aichholzer (dir. tes.) , Ferran Hurtado Díaz (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2007
• Idioma: español
• Tribunal Calificador de la Tesis: Oriol Serra Albó (presid.) , Pedro Antonio Ramos Alonso (secret.) , Jorge Urrutia Galicia (voc.) , Franz Aurenhammer (voc.) , Alfredo García Olaverri (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • Abstract The study of geometric graphs is part of discrete and combinatorial geometry and also includes aspects of computational geometry and graph theory, The vertices of a geometric graph are points in the plane and the arcs are straight-line edges connecting pairs of points. We investigate non-crossing geometric graphs, meaning that no two edges of a geometric graph have an interior point in common. We address fundamental problems on counting and listing such graphs, and also consider structural problems for geometric graphs.

    A main topic of this thesis is the enumeration of geometric graphs. A longstanding open problem asks for the maximum number of triangulations among all point sets of a given cardinality. We exhibit sets of n points having v72n triangulations, which improves over the previous known examples to maximize the number of triangulations. We further show that the number of geometric graphs is minimized for point sets in convex position.

    We then provide a method for listing geometric graphs in Gray code order. Two consecutive graphs in this listing only differ by an edge. This also allows to list plane spanning trees and connected plane graphs on a given set of n points in O(n log n) time per graph. Gray code enumeration for geometric graphs has only been known for graphs on point sets in convex position so far.

    Then we consider subgraphs of geometric graphs, asking how many edges can be removed from any complete geometric graph, such that the remaining graph is guaranteed to still contain a certain sub-configuration. We obtain tight bounds for the case of perfect matchings and spanning forests with a given number of components.

    Finally, we investigate a structural property of triangulations, namely whether every triangulation contains a pointed spanning tree as a subgraph. We answer this question negatively and thereby present a solution to Problem 50 of the Open Problems Project, a list of prominent open problems in computational geometry an