An analysis of heuristics for graph planarization

DOI10.1080/02522667.1997.10699312zbMath0878.68095OpenAlexW2000695501MaRDI QIDQ4354090

Robert J. Cimikowski

Publication date: 4 January 1998

Published in: Journal of Information and Optimization Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02522667.1997.10699312

zbMATH Keywords

graph planarizationedge addition method

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Branch-and-bound techniques for the maximum planar subgraph problem^∗ ⋮ The Effect of Planarization on Width ⋮ The Effect of Planarization on Width ⋮ Heuristics for the maximum outerplanar subgraph problem

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Graph theory applications
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
• Alpha-algorithms for incremental planarity testing (preliminary version)
• Efficient Planarity Testing
• An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
• An efficient graph planarization two‐phase heuristic