A simulated annealing algorithm for the maximum planar subgraph problem

DOI10.1080/00207160410001684352MaRDI QIDQ4831415zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Heuristics for the maximum outerplanar subgraph problem
• Publication:4886062
• A Better Approximation Algorithm for Finding Planar Subgraphs
• A note on the practicality of maximal planar subgraph algorithms
• A linear algorithm for the maximal planar subgraph problem

Cites work

• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 1488569 (Why is no real title available?)
• A Better Approximation Algorithm for Finding Planar Subgraphs
• A GRASP for graph planarization
• A new planarity test
• An efficient graph planarization two‐phase heuristic
• Branch-and-bound techniques for the maximum planar subgraph problem^∗
• Efficient Planarity Testing
• Fully dynamic planarity testing with applications
• Local Search Algorithms for the Maximal Planar Layout Problem
• Maximum planar subgraphs and nice embeddings: Practical layout tools
• On the thickness and arboricity of a graph
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• 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
• The thickness of graphs: A survey

Cited in

(7)

• A simulated annealing algorithm for determining the thickness of a graph
• An improved algorithm for finding maximum outerplanar subgraphs
• Heuristics for the maximum outerplanar subgraph problem
• A linear algorithm for the maximal planar subgraph problem
• Two new approximation algorithms for the maximum planar subgraph problem
• scientific article; zbMATH DE number 3978858 (Why is no real title available?)
• Analysis of heuristics for finding a maximum weight planar subgraph

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: A simulated annealing algorithm for the maximum planar subgraph problem

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