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

^∗ Supported by a grant from the Engineering Experiment Station, Montana State University

Abstract

We present branch-and-bound algorithms for finding a maximum planar subgraph of a nonplanar graph. The problem has important applicatons in circuit layout, automated graph drawing, and facility layout. The algorithms described utilize heuristics to obtain an initial lower bound for the size of a maximum planar subgraph, then apply a sequence of fast preliminary tests for planarity to eliminate infeasible partial solutions. Computational experience is reported from testing the algorithms on a set of random nonplanar graphs and is encouraging. A best-first search technique is shown to be a practical approach to solving problems of moderate size.

Keywords:

• Maximum planar subgraph
• branch-and-bound
• planar graph
• graph planarization
• NP-hard
• planarity

^∗ Supported by a grant from the Engineering Experiment Station, Montana State University

^∗ Supported by a grant from the Engineering Experiment Station, Montana State University

Notes

^∗ Supported by a grant from the Engineering Experiment Station, Montana State University