A simulated annealing algorithm for the maximum planar subgraph problem

DOI10.1080/00207160410001684352zbMATH Open1055.05144OpenAlexW2003965618MaRDI QIDQ4831415FDOQ4831415

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

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

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)

Cites Work

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

Cited In (7)

• Two new approximation algorithms for the maximum planar subgraph problem
• A simulated annealing algorithm for determining the thickness of a graph
• Analysis of heuristics for finding a maximum weight planar subgraph
• An improved algorithm for finding maximum outerplanar subgraphs
• A linear algorithm for the maximal planar subgraph problem
• Heuristics for the maximum outerplanar subgraph problem
• Title not available (Why is that?)

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)