A simulated annealing algorithm for the maximum planar subgraph problem

DOI10.1080/00207160410001684352zbMath1055.05144OpenAlexW2003965618MaRDI QIDQ4831415

Timo Poranen

Publication date: 29 December 2004

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

simulated annealingmaximum planar subgraphgraph planarization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An improved algorithm for finding maximum outerplanar subgraphs ⋮ Heuristics for the maximum outerplanar subgraph problem

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• On the thickness and arboricity of a graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The thickness of graphs: A survey
• The sizes of maximal planar, outerplanar, and bipartite planar subgraphs
• Maximum planar subgraphs and nice embeddings: Practical layout tools
• A new planarity test
• Fully dynamic planarity testing with applications
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Efficient Planarity Testing
• A Better Approximation Algorithm for Finding Planar Subgraphs
• An efficient graph planarization two‐phase heuristic
• A GRASP for graph planarization
• Branch-and-bound techniques for the maximum planar subgraph problem^∗
• Local Search Algorithms for the Maximal Planar Layout Problem