Back to Search
Start Over
On the k-restricted structure ratio in planar and outerplanar graphs.
- Source :
-
Discrete Mathematics & Theoretical Computer Science (DMTCS) . Dec2008, Vol. 10 Issue 3, p135-147. 13p. 6 Diagrams. - Publication Year :
- 2008
-
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 MaximumWeight 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 ½. 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- 10
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics & Theoretical Computer Science (DMTCS)
- Publication Type :
- Academic Journal
- Accession number :
- 41020763