episciences.org_423_1675067424
1675067424
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
01
01
2008
Vol. 10 no. 3
Graph and Algorithms
On the krestricted structure ratio in planar and outerplanar graphs
Gruia
Călinescu
Cristina G.
Fernandes
https://orcid.org/0000000252592859
Graphs and Algorithms
A planar krestricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar krestricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar krestricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum krestricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar krestricted 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.
01
01
2008
423
National Science Foundation
0515088
https://hal.science/hal00972327v1
10.46298/dmtcs.423
https://dmtcs.episciences.org/423

https://dmtcs.episciences.org/423/pdf

https://dmtcs.episciences.org/423/pdf