An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem (1993)

Previous article Next article An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph ProblemJiazhen Cai, Xiaofeng Han, and Robert E. TarjanJiazhen Cai, Xiaofeng Han, and Robert E. Tarjanhttps://doi.org/10.1137/0222068PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstractBased on a new version of the Hopcroft and Tarjan planarity testing algorithm, this paper develops an $O(m\log n)$-time algorithm to find a maximal planar subgraph.[1] Kellogg S. Booth and , George S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using $PQ$-tree algorithms, J. Comput. System Sci., 13 (1976), 335–379 55:6932 0367.68034 CrossrefISIGoogle Scholar[2] Norishige Chiba, , Takao Nishizeki, , Shigenobu Abe and , Takao Ozawa, A linear algorithm for embedding planar graphs using $PQ$-trees, J. Comput. System Sci., 30 (1985), 54–76 10.1016/0022-0000(85)90004-2 86g:05030 0605.68060 CrossrefISIGoogle Scholar[3] G. Di Battista and , R. Tamassia, Incremental planarity testing (extended abstract), Proc. 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, 436–441 Google Scholar[4] Shimon Even and , Robert Endre Tarjan, Computing an $st$-numbering, Theoret. Comput. Sci., 2 (1976), 339–344 10.1016/0304-3975(76)90086-4 54:2508 0341.68029 CrossrefGoogle Scholar[5] M. Garey and , D. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979x+338 80g:68056 0411.68039 Google Scholar[6] D. Hall and , G. Spencer, Elementary topology, John Wiley & Sons Inc., New York, 1955xii+303 17,649a Google Scholar[7] John Hopcroft and , Robert Tarjan, Efficient planarity testing, J. Assoc. Comput. Mach., 21 (1974), 549–568 10.1145/321850.321852 50:11841 0307.68025 CrossrefISIGoogle Scholar[8] E. Horowitz and , S. Sahni, Fundamentals of Data Structure, Computer Science Press, Rockville, MD, 1983 Google Scholar[9] R. Jayakumar, , K. Thulasiraman and , M. N. S. Swamp, $O(n^2)$ algorithms for graph planarization, IEEE Trans. CAD, 8 (1989), 257–267 10.1109/43.21845 CrossrefISIGoogle Scholar[10] N. Kobayashi, , S. Masuda and , T. Kashiwabara, Algorithms to obtain a maximal planar Hamilton subgraph, IEICE Transactions, E74 (1991), 657–664 Google Scholar[11] A. Lempel, , S. Even and , I. Cederbaum, An algorithm for planarity testing of graphsTheory of Graphs (Internat. Sympos., Rome, 1966), Gordon and Breach, New York, 1967, 215–232, Italy, July 36:3669 0197.50204 Google Scholar[12] Robert Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput., 1 (1972), 146–160 10.1137/0201010 46:3313 0251.05107 LinkGoogle Scholar[13] Robert Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1984 Google Scholar[14] Wolfgang J. Thron, Introduction to the theory of functions of a complex variable, John Wiley & Sons Inc., New York, 1953x+230 14,857b 0050.07503 Google Scholar[15] W. Wu, On the planar imbedding of linear graphs. I, J. Systems Sci. Math. Sci., 5 (1985), 290–302 87i:05091a 0601.05017 Google ScholarKeywordsalgorithmcomplexitydepth-first-searchembeddingplanar graphselection tree Previous article Next article FiguresRelatedReferencesCited ByDetails Exact Algorithms for the Maximum Planar Subgraph ProblemACM Journal of Experimental Algorithmics, Vol. 24 | 17 Dec 2019 Cross Ref Finding Triangles for Maximum Planar SubgraphsWALCOM: Algorithms and Computation | 21 February 2017 Cross Ref PMPSO: A near-optimal graph planarization algorithm using probability model based particle swarm optimization2015 IEEE International Conference on Progress in Informatics and Computing (PIC) | 1 Dec 2015 Cross Ref Graph planarization problem optimization based on triple-valued gravitational search algorithmIEEJ Transactions on Electrical and Electronic Engineering, Vol. 9, No. 1 | 9 December 2013 Cross Ref An Effective Ant Colony Algorithm for Graph Planarization ProblemBio-Inspired Computing and Applications | 1 Jan 2012 Cross Ref Metamodel Matching Based on Planar Graph Edit DistanceTheory and Practice of Model Transformations | 1 Jan 2010 Cross Ref Experiments on exact crossing minimization using column generationACM Journal of Experimental Algorithmics, Vol. 14 | 1 Dec 2009 Cross Ref Non-planar core reduction of graphsDiscrete Mathematics, Vol. 309, No. 7 | 1 Apr 2009 Cross Ref A self-stabilizing algorithm for the maximum planarization problem in complete bipartite networksInformation Processing Letters, Vol. 109, No. 10 | 1 Apr 2009 Cross Ref A Multi-Layered Immune System for Graph Planarization ProblemIEICE Transactions on Information and Systems, Vol. E92-D, No. 12 | 1 Jan 2009 Cross Ref A new neural network algorithm for planarization problemsScience in China Series F: Information Sciences, Vol. 51, No. 12 | 27 August 2008 Cross Ref A branch-and-cut approach to the crossing number problemDiscrete Optimization, Vol. 5, No. 2 | 1 May 2008 Cross Ref A Linear-Time Algorithm for Finding a Maximal Planar SubgraphHristo N. DjidjevSIAM Journal on Discrete Mathematics, Vol. 20, No. 2 | 1 August 2006AbstractPDF (200 KB)A simulated annealing algorithm for determining the thickness of a graphInformation Sciences, Vol. 172, No. 1-2 | 1 Jun 2005 Cross Ref A Linear Time Algorithm for Finding a Maximal Planar Subgraph Based on PC-TreesComputing and Combinatorics | 1 Jan 2005 Cross Ref Automatic Layout of UML Class Diagrams in Orthogonal StyleInformation Visualization, Vol. 3, No. 3 | 22 July 2004 Cross Ref Technical FoundationsGraph Drawing Software | 1 Jan 2004 Cross Ref An efficient parallel algorithm for planarization problemIEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, Vol. 49, No. 3 | 1 Mar 2002 Cross Ref An Algorithm for Finding Large Induced Planar SubgraphsGraph Drawing | 21 February 2002 Cross Ref A genetic algorithm for determining the thickness of a graphInformation Sciences, Vol. 138, No. 1-4 | 1 Oct 2001 Cross Ref Software PackagesDrawing Graphs | 25 April 2001 Cross Ref Graph Drawing**Work supported in part by the National Science Foundation under grant CCR-9732327, and by the U.S. Army Research Office under grant DAAH04-96-1-0013.Handbook of Computational Geometry | 1 Jan 2000 Cross Ref Algorithm 797ACM Transactions on Mathematical Software, Vol. 25, No. 3 | 1 Sep 1999 Cross Ref A new planarity testTheoretical Computer Science, Vol. 223, No. 1-2 | 1 Jul 1999 Cross Ref The Constrained Crossing Minimization Problem A First ApproachOperations Research Proceedings 1998 | 1 Jan 1999 Cross Ref A note on computing a maximal planar subgraph using PQ-treesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 17, No. 7 | 1 Jul 1998 Cross Ref A Better Approximation Algorithm for Finding Planar SubgraphsJournal of Algorithms, Vol. 27, No. 2 | 1 May 1998 Cross Ref An analysis of heuristics for graph planarizationJournal of Information and Optimization Sciences, Vol. 18, No. 1 | 1 Jan 1997 Cross Ref On-Line Planarity TestingGiuseppe Di Battista and Roberto TamassiaSIAM Journal on Computing, Vol. 25, No. 5 | 31 July 2006AbstractPDF (5139 KB)Gap strings and spanning forests for bridge graphs of biconnected graphsDiscrete Applied Mathematics, Vol. 69, No. 1-2 | 1 Aug 1996 Cross Ref Maximum planar subgraphs and nice embeddings: Practical layout toolsAlgorithmica, Vol. 16, No. 1 | 1 Jul 1996 Cross Ref Graph drawing methodsConceptual Structures: Knowledge Representation as Interlingua | 8 July 2005 Cross Ref A practical approach to static node positioningGraph Drawing | 1 June 2005 Cross Ref A linear algorithm for the maximal planar subgraph problemAlgorithms and Data Structures | 1 June 2005 Cross Ref Planarization of graphs embedded on surfacesGraph-Theoretic Concepts in Computer Science | 2 June 2005 Cross Ref A linear time algorithm for finding maximal planar subgraphsAlgorithms and Computations | 9 June 2005 Cross Ref Branch-and-bound techniques for the maximum planar subgraph problem ∗International Journal of Computer Mathematics, Vol. 53, No. 3-4 | 1 Jan 1994 Cross Ref Graph PlanarizationEncyclopedia of Optimization Cross Ref Graph PlanarizationEncyclopedia of Optimization Cross Ref Volume 22, Issue 6| 1993SIAM Journal on Computing1117-1349 History Submitted:05 June 1989Accepted:01 April 1992Published online:31 July 2006 InformationCopyright © 1993 © Society for Industrial and Applied MathematicsKeywordsalgorithmcomplexitydepth-first-searchembeddingplanar graphselection treeMSC codes68R1068Q3594C15PDF Download Article & Publication DataArticle DOI:10.1137/0222068Article page range:pp. 1142-1162ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics