Oswin Aichholzer ; Sergio Cabello ; Ruy Fabila-Monroy ; David Flores-Peñaloza ; Thomas Hackl et al. - Edge-Removal and Non-Crossing Configurations in Geometric Graphs

dmtcs:525 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 1 - https://doi.org/10.46298/dmtcs.525
Edge-Removal and Non-Crossing Configurations in Geometric Graphs

Authors: Oswin Aichholzer ; Sergio Cabello ORCID-iD; Ruy Fabila-Monroy ; David Flores-Peñaloza ; Thomas Hackl ; Clemens Huemer ; Ferran Hurtado ; David R. Wood ORCID-iD

    A geometric graph is a graph G = (V, E) drawn in the plane, such that V is a point set in general position and E is a set of straight-line segments whose endpoints belong to V. We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete geometric graph with n vertices such that the remaining graph still contains a certain non-crossing subgraph. The non-crossing subgraphs that we consider are perfect matchings, subtrees of a given size, and triangulations. In each case, we obtain tight bounds on the maximum number of removable edges.


    Volume: Vol. 12 no. 1
    Section: Graph and Algorithms
    Published on: January 1, 2010
    Imported on: March 26, 2015
    Keywords: extremal graph theory,geometric graph,perfect matching,spanning tree,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

    Share

    Consultation statistics

    This page has been seen 263 times.
    This article's PDF has been downloaded 261 times.