A simulated annealing algorithm for the maximum planar subgraph problem

DOI10.1080/00207160410001684352zbMath1055.05144MaRDI 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 annealing; maximum planar subgraph; graph planarization

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

90C59: Approximation methods and heuristics in mathematical programming

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Heuristics for the maximum outerplanar subgraph problem

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• 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
• Branch-and-bound techniques for the maximum planar subgraph problem^∗
• Local Search Algorithms for the Maximal Planar Layout Problem