 |
Discrete Mathematics & Theoretical Computer Science |
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
2; Ruy Fabila-Monroy 3; David Flores-Peñaloza 4; Thomas Hackl 1; Clemens Huemer 5; Ferran Hurtado 6; David R. Wood 7
- 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]
Graphs and Algorithms
[en]
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.