License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.23
URN: urn:nbn:de:0030-drops-89589
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8958/
Go to the corresponding LIPIcs Volume Portal

Huang, Shixun ; Bao, Zhifeng ; Culpepper, J. Shane ; Zhang, Ping ; Zhang, Bang

A Linear-Time Algorithm for Finding Induced Planar Subgraphs

pdf-format:
LIPIcs-SEA-2018-23.pdf (1 MB)

Abstract

In this paper we study the problem of efficiently and effectively extracting induced planar subgraphs. Edwards and Farr proposed an algorithm with O(mn) time complexity to find an induced planar subgraph of at least 3n/(d+1) vertices in a graph of maximum degree d. They also proposed an alternative algorithm with O(mn) time complexity to find an induced planar subgraph graph of at least 3n/(bar{d}+1) vertices, where bar{d} is the average degree of the graph. These two methods appear to be best known when d and bar{d} are small. Unfortunately, they sacrifice accuracy for lower time complexity by using indirect indicators of planarity. A limitation of those approaches is that the algorithms do not implicitly test for planarity, and the additional costs of this test can be significant in large graphs. In contrast, we propose a linear-time algorithm that finds an induced planar subgraph of n-nu vertices in a graph of n vertices, where nu denotes the total number of vertices shared by the detected Kuratowski subdivisions. An added benefit of our approach is that we are able to detect when a graph is planar, and terminate the reduction. The resulting planar subgraphs also do not have any rigid constraints on the maximum degree of the induced subgraph. The experiment results show that our method achieves better performance than current methods on graphs with small skewness.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2018:8958,
  author =	{Shixun Huang and Zhifeng Bao and J. Shane Culpepper and Ping Zhang and Bang Zhang},
  title =	{{A Linear-Time Algorithm for Finding Induced Planar Subgraphs}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8958},
  URN =		{urn:nbn:de:0030-drops-89589},
  doi =		{10.4230/LIPIcs.SEA.2018.23},
  annote =	{Keywords: induced planar subgraphs, experimental analysis}
}

Keywords: induced planar subgraphs, experimental analysis
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI