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]

This page has been seen 72 times.

This article's PDF has been downloaded 131 times.