Edge-Removal and Non-Crossing Configurations in Geometric Graphs

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.75-86
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990435
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:36:53
Dernière modification le : mercredi 29 novembre 2017 - 10:26:18
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:24:09

Fichier

985-4942-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990435, version 1

Collections

Citation

Oswin Aichholzer, Sergio Cabello, Ruy Fabila-Monroy, David Flores-Peñaloza, Thomas Hackl, et al.. Edge-Removal and Non-Crossing Configurations in Geometric Graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (1), pp.75-86. 〈hal-00990435〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

224