Document Open Access Logo

A Linear-Time Algorithm for Finding Induced Planar Subgraphs

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

PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.23.pdf
  • Filesize: 1.46 MB
  • 15 pages

Document Identifiers

Author Details

Shixun Huang
  • RMIT University, Melbourne, Australia
Zhifeng Bao
  • RMIT University, Melbourne, Australia
J. Shane Culpepper
  • RMIT University, Melbourne, Australia
Ping Zhang
  • Wuhan University, Wuhan, China
Bang Zhang
  • DATA61 — CSIRO, Australia

Funding

This work was supported by ARC (DP170102726, DP170102231, DP180102050), NSF of China (61728204, 91646204). Zhifeng Bao is a recipient of Google Faculty Award.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.SEA.2018.23

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • induced planar subgraphs
  • experimental analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G Tollis. Graph drawing: Algorithms for the visualization of graphs. Prentice Hall PTR, 1998. Google Scholar
  2. Itai Benjamini and Oded Schramm. Harmonic functions on planar and almost planar graphs and manifolds, via circle packings. Inventiones Mathematicae, 126(3):565-587, 1996. Google Scholar
  3. John M Boyer and Wendy J Myrvold. On the cutting edge: Simplified o(n) planarity by edge addition. J. Graph Algorithms Appl., 8(2):241-273, 2004. Google Scholar
  4. Sergio Cabello and Bojan Mohar. Crossing and weighted crossing number of near-planar graphs. In Proc. GD, pages 38-49. Springer, 2008. Google Scholar
  5. Gek L Chia and Chan L Lee. Regular raphs with small skewness and crossing numbers. Bulletin of the Malaysian Mathematical Sciences Society, 39(4):1687-1693, 2016. Google Scholar
  6. Robert J Cimikowski. Graph planarization and skewness. Congressus Numerantium, pages 21-21, 1992. Google Scholar
  7. Alice M Dean, William S Evans, Ellen Gethner, Joshua D Laison, Mohammad Ali Safari, and William T Trotter. Bar k-visibility graphs. J. Graph Algorithms Appl., 11(1):45-59, 2007. Google Scholar
  8. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G Tollis. Algorithms for drawing graphs: an annotated bibliography. Computational Geometry, 4(5):235-282, 1994. Google Scholar
  9. Walter Didimo and Giuseppe Liotta. The crossing-angle resolution in graph drawing. In Thirty Essays on Geometric Graph Theory, pages 167-184. Springer, 2013. Google Scholar
  10. Keith Edwards and Graham Farr. An algorithm for finding large induced planar subgraphs. In Proc. GD, pages 75-83. Springer, 2001. Google Scholar
  11. Keith Edwards and Graham Farr. Planarization and fragmentability of some classes of graphs. Discrete Mathematics, 308(12):2396-2406, 2008. Google Scholar
  12. William Evans, Michael Kaufmann, William Lenhart, Tamara Mchedlidze, and Stephen Wismath. Bar 1-visibility graphs and their relation to other nearly planar graphs. J. Graph Algorithms Appl, 18(5):721-739, 2014. Google Scholar
  13. Alan Gibbons. Algorithmic graph theory. Cambridge university press, 1985. Google Scholar
  14. Magnús M Halldórsson and Hoong Chuin Lau. Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring. In Graph Algorithms And Applications I, pages 45-57. World Scientific, 2002. Google Scholar
  15. Mohsen MD Hassan and Gary L Hogg. A review of graph theory application to the facilities layout problem. Omega, 15(4):291-300, 1987. Google Scholar
  16. Petr Hliněnỳ and Gelasio Salazar. On the crossing number of almost planar graphs. In Proc. GD, pages 162-173. Springer, 2006. Google Scholar
  17. Seok-Hee Hong, Peter Eades, Giuseppe Liotta, and Sheung-Hung Poon. Fáry’s theorem for 1-planar graphs. In Proc. COCOON, pages 335-346, 2012. Google Scholar
  18. Michael Jünger and Petra Mutzel. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica, 16(1):33-59, 1996. Google Scholar
  19. Mukkai S Krishnamoorthy and Narsingh Deo. Node-deletion np-complete problems. SIAM Journal on Computing, 8(4):619-625, 1979. Google Scholar
  20. Jérôme Kunegis. KONECT: The koblenz network collection. In Proc. WWW, pages 1343-1350, 2013. Google Scholar
  21. Casimir Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta Mathematicae, 15(1):271-283, 1930. Google Scholar
  22. Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2015. URL: http://snap.stanford.edu/data.
  23. John M Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. Google Scholar
  24. Annegret Liebers. Planarizing graphs—a survey and annotated bibliography. In Graph Algorithms And Applications 2, pages 257-330. World Scientific, 2004. Google Scholar
  25. László Lovász. On decomposition of graphs. Studia Sci. Math. Hungar, 1(273):238, 1966. Google Scholar
  26. Carsten Lund and Mihalis Yannakakis. The approximation of maximum subgraph problems. In Proc. ICALP, pages 40-51. Springer, 1993. Google Scholar
  27. Kerri Morgan and Graham Farr. Approximation algorithms for the maximum induced planar and outerplanar subgraph problems. J. Graph Algorithms Appl., 11(1):165-193, 2007. Google Scholar
  28. Mauricio GC Resende and Celso C Ribeiro. A grasp for graph planarization. Networks, 29(3):173-189, 1997. Google Scholar
  29. Robert Tarjan. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2):146-160, 1972. Google Scholar
  30. Douglas Brent West et al. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001. Google Scholar
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