An algorithm for finding large induced planar subgraphs

Keith Edwards, Graham E Farr

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    8 Citations (Scopus)

    Abstract

    This paper presents an efficient algorithm that finds an induced planar subgraph of at least 3n/(d + 1) vertices in a graph of n vertices and maximum degree d. This bound is sharp for d = 3, in the sense that if ɛ > 3/4 then there are graphs of maximum degree 3 with no induced planar subgraph of at least ɛn vertices. Our performance ratios appear to be the best known for small d. For example, when d = 3, our performance ratio of at least 3/4 compares with the ratio 1/2 obtained by Halldórsson and Lau. Our algorithm builds up an induced planar subgraph by iteratively adding a new vertex to it, or swapping a vertex in it with one outside it, in such a way that the procedure is guaranteed to stop, and so as to preserve certain properties that allow its performance to be analysed. This work is related to the authors’ work on fragmentability of graphs.
    Original languageEnglish
    Title of host publicationGraph Drawing
    Subtitle of host publication9th International Symposium, GD 2001 Vienna, Austria, September 23-26, 2001 Revised Papers
    EditorsPetra Mutzel, Michael Junger, Sebastian Leipert
    Place of PublicationBerlin Germany
    PublisherSpringer
    Pages75-83
    Number of pages9
    ISBN (Print)3540433090
    DOIs
    Publication statusPublished - 2002
    EventGraph Drawing 2001 - Vienna, Austria
    Duration: 23 Sep 200126 Sep 2001
    Conference number: 9th
    https://link.springer.com/book/10.1007/3-540-45848-4 (Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume2265
    ISSN (Print)0302-9743

    Conference

    ConferenceGraph Drawing 2001
    Abbreviated titleGD 2001
    CountryAustria
    CityVienna
    Period23/09/0126/09/01
    Internet address

    Cite this

    Edwards, K., & Farr, G. E. (2002). An algorithm for finding large induced planar subgraphs. In P. Mutzel, M. Junger, & S. Leipert (Eds.), Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23-26, 2001 Revised Papers (pp. 75-83). (Lecture Notes in Computer Science; Vol. 2265). Springer. https://doi.org/10.1007/3-540-45848-4_6