An analysis of heuristics for graph planarization

DOI10.1080/02522667.1997.10699312MaRDI QIDQ4354090zbMATH OpenOpenAlexFDO

Authors 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

edge addition methodgraph planarization

Mathematics Subject Classification ID

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

Recommendations

• An efficient graph planarization two‐phase heuristic
• scientific article; zbMATH DE number 910888
• Analysis of heuristics for finding a maximum weight planar subgraph
• A GRASP for graph planarization
• An analysis of some linear graph layout heuristics
• A graph approximation heuristic for the vertex cover problem on planar graphs
• A linear time heuristic for the branch-decomposition of planar graphs
• A heuristic for the coloring of planar graphs
• scientific article; zbMATH DE number 220337
• Planarizing graphs---a survey and annotated bibliography

Cites work

• Alpha-algorithms for incremental planarity testing (extended abstract)
• An O(m\log n)-Time Algorithm for the Maximal Planar Subgraph Problem
• An efficient graph planarization two‐phase heuristic
• Efficient Planarity Testing
• 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

Cited in

(14)

• Non-planar core reduction of graphs
• Analysis of heuristics for finding a maximum weight planar subgraph
• A new neural network algorithm for planarization problems
• Heuristics for the maximum outerplanar subgraph problem
• scientific article; zbMATH DE number 434681 (Why is no real title available?)
• An efficient graph planarization two‐phase heuristic
• The effect of planarization on width
• Branch-and-bound techniques for the maximum planar subgraph problem^∗
• scientific article; zbMATH DE number 910888 (Why is no real title available?)
• The effect of planarization on width
• On the planarization of wireless sensor networks
• Graph Drawing
• O(n2) algorithms for graph planarization
• Local optimization algorithms for maximum planar subgraph

This page was built for publication: An analysis of heuristics for graph planarization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4354090)