On the k-restricted structure ratio in planar and outerplanar graphs

Abstract : A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1 = 2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.135--147
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00972327
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 3 avril 2014 - 16:13:22
Dernière modification le : mercredi 29 novembre 2017 - 10:26:18
Document(s) archivé(s) le : jeudi 3 juillet 2014 - 16:36:12

Fichier

961-3711-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00972327, version 1

Collections

Citation

Gruia Călinescu, Cristina G. Fernandes. On the k-restricted structure ratio in planar and outerplanar graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (3), pp.135--147. 〈hal-00972327〉

Partager

Métriques

Consultations de la notice

208

Téléchargements de fichiers

70