### On the k-Structure Ratio in Planar and Outerplanar Graphs

*Gruia Calinescu, Cristina G. Fernandes*

#### 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.

Full Text: PDF PostScript