Gruia Călinescu ; Cristina G. Fernandes - On the k-restricted structure ratio in planar and outerplanar graphs

dmtcs:423 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 3 - https://doi.org/10.46298/dmtcs.423
On the k-restricted structure ratio in planar and outerplanar graphs

Authors: Gruia Călinescu ; Cristina G. Fernandes ORCID-iD

    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.


    Volume: Vol. 10 no. 3
    Section: Graph and Algorithms
    Published on: January 1, 2008
    Imported on: March 26, 2015
    Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Fundings :
      Source : OpenAIRE Research Graph
    • Approximation Algorithms for Networks; Funder: National Science Foundation; Code: 0515088

    Share

    Consultation statistics

    This page has been seen 246 times.
    This article's PDF has been downloaded 152 times.