10.46298/dmtcs.423
https://dmtcs.episciences.org/423
Călinescu, Gruia
Gruia
Călinescu
Fernandes, Cristina G.
Cristina G.
Fernandes
0000-0002-5259-2859
National Science Foundation
0515088
Approximation Algorithms for Networks
On the k-restricted structure ratio in planar and outerplanar graphs
Graphs and Algorithms
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.
episciences.org
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
2015-06-09
2008-01-01
2008-01-01
en
journal article
https://hal.science/hal-00972327v1
1365-8050
https://dmtcs.episciences.org/423/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
Vol. 10 no. 3
Graph and Algorithms
Researchers
Students