1 Search Results for "Zhang, Ping"

Document
DOI: 10.4230/LIPIcs.SEA.2018.23
A Linear-Time Algorithm for Finding Induced Planar Subgraphs

Authors: Shixun Huang, Zhifeng Bao, J. Shane Culpepper, Ping Zhang, and Bang Zhang

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

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.
Cite as

Shixun Huang, Zhifeng Bao, J. Shane Culpepper, Ping Zhang, and Bang Zhang. A Linear-Time Algorithm for Finding Induced Planar Subgraphs. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.SEA.2018.23,
  author =	{Huang, Shixun and Bao, Zhifeng and Culpepper, J. Shane and Zhang, Ping and Zhang, Bang},
  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 =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.23},
  URN =		{urn:nbn:de:0030-drops-89589},
  doi =		{10.4230/LIPIcs.SEA.2018.23},
  annote =	{Keywords: induced planar subgraphs, experimental analysis}
}
  • Refine by Author
  • 1 Bao, Zhifeng
  • 1 Culpepper, J. Shane
  • 1 Huang, Shixun
  • 1 Zhang, Bang
  • 1 Zhang, Ping

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms

  • Refine by Keyword
  • 1 experimental analysis
  • 1 induced planar subgraphs

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact