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 Graphs

Authors: Oswin Aichholzer ; Sergio Cabello ; Ruy Fabila-Monroy ; David Flores-Peñaloza ; Thomas Hackl ; Clemens Huemer ; Ferran Hurtado ; David R. Wood

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]


Share

Consultation statistics

This page has been seen 163 times.
This article's PDF has been downloaded 204 times.