Skip to Main content Skip to Navigation
Journal articles

Edge-Removal and Non-Crossing Configurations in Geometric Graphs

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:36:53 PM
Last modification on : Monday, November 16, 2020 - 3:56:03 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:24:09 PM


Files produced by the author(s)


  • HAL Id : hal-00990435, version 1



Oswin Aichholzer, Sergio Cabello, Ruy Fabila-Monroy, David Flores-Peñaloza, Thomas Hackl, et al.. Edge-Removal and Non-Crossing Configurations in Geometric Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.75-86. ⟨hal-00990435⟩



Record views


Files downloads