Authors: Oswin Aichholzer ¹; Sergio Cabello ²; Ruy Fabila-Monroy ³; David Flores-Peñaloza ⁴; Thomas Hackl ¹; Clemens Huemer ⁵; Ferran Hurtado ⁶; David R. Wood ⁷

• 1 Institute for Software Technology [Graz]
• 2 Departement of Mathematics [Slovenia]
• 3 Centro de Investigacion y de Estudios Avanzados del Instituto Politécnico Nacional
• 4 Departamento de Matematicas [Mexico]
• 5 Applied Mathematics IV Department
• 6 Departament de Matemàtica Aplicada II
• 7 Department of Mathematics and Statistics [Melbourne]

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.