Planarization and fragmentability of some classes of graphs

Keith Edwards, Graham Farr

    Research output: Contribution to journalArticlepeer-review

    12 Citations (Scopus)

    Abstract

    The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give firagmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of k-colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most (d) over bar in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most ((d) over bar - 2)/((d) over bar + 1), provided (d) over bar >= 4 or the graph is connected and (d) over bar >= 2. The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs. (C) 2007 Elsevier B.V. All rights reserved.

    Original languageEnglish
    Pages (from-to)2396-2406
    Number of pages11
    JournalDiscrete Mathematics
    Volume308
    Issue number12
    DOIs
    Publication statusPublished - 28 Jun 2008

    Keywords

    • planarity
    • planarization
    • fragmentability
    • induced planar subgraph
    • induced series-parallel subgraph
    • algorithm
    • THICKNESS

    Cite this