Aichholzer, Oswin and Cabello, Sergio and Fabila-Monroy, Ruy and Flores-Peñaloza, David and Hackl, Thomaset al. - Edge-Removal and Non-Crossing Configurations in Geometric Graphs

dmtcs:525 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 1
Edge-Removal and Non-Crossing Configurations in Geometric Graphs

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

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.


Source : oai:HAL:hal-00990435v1
Volume: Vol. 12 no. 1
Section: Graph and Algorithms
Published on: January 1, 2010
Submitted 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

Browsing statistics

This page has been seen 43 times.
This article's PDF has been downloaded 82 times.