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 GraphsArticle

Authors: Oswin Aichholzer 1; Sergio Cabello ORCID2; Ruy Fabila-Monroy 3; David Flores-Peñaloza 4; Thomas Hackl 1; Clemens Huemer 5; Ferran Hurtado 6; David R. Wood ORCID7

  • 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.

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]

4 Documents citing this article

Consultation statistics

This page has been seen 448 times.
This article's PDF has been downloaded 392 times.