Branch-and-bound techniques for the maximum planar subgraph problem∗

DOI10.1080/00207169408804320MaRDI QIDQ4844576zbMATH OpenOpenAlexFDO

Authors Robert J. Cimikowski

Publication date 10 October 1995

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

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

zbMATH Keywords

branch-and-bound algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 910888
• Maximum planar subgraphs and nice embeddings: Practical layout tools
• An efficient graph planarization two‐phase heuristic
• A Better Approximation Algorithm for Finding Planar Subgraphs
• Analysis of heuristics for finding a maximum weight planar subgraph

Cites work

• A batching method for coloring planar graphs
• A linear algorithm for embedding planar graphs using PQ-trees
• An O(m\log n)-Time Algorithm for the Maximal Planar Subgraph Problem
• An algorithm for finding a maximum weighted independent set in an arbitrary graph
• An analysis of heuristics for graph planarization
• An efficient graph planarization two‐phase heuristic
• An Efficient Heuristic Procedure for Partitioning Graphs
• Efficient Planarity Testing
• Facilities Layout Adjacency Determination: An Experimental Comparison of Three Graph Theoretic Heuristics
• Finding a Maximum Clique in an Arbitrary Graph
• Finding a Maximum Independent Set
• scientific article; zbMATH DE number 3668651 (Why is no real title available?)
• On linear-time algorithms for five-coloring planar graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(5)

• Maximum planar subgraphs and nice embeddings: Practical layout tools
• Heuristics for the maximum outerplanar subgraph problem
• An efficient graph planarization two‐phase heuristic
• A simulated annealing algorithm for the maximum planar subgraph problem
• scientific article; zbMATH DE number 910888 (Why is no real title available?)

This page was built for publication: Branch-and-bound techniques 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 Q4844576)