Edge-Removal and Non-Crossing Configurations in Geometric Graphs
Oswin Aichholzer, Sergio Cabello, Ruy Fabila-Monroy, David Flores-Peñaloza, Thomas Hackl, Clemens Huemer, Ferran Hurtado, David R. Wood
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.
Full Text: PDF PostScript