Solving the Maximum Weight Planar Subgraph Problem by Branch-and-Cut
Jünger, Michael and Mutzel, Petra
Solving the Maximum Weight Planar Subgraph Problem by Branch-and-Cut.
Published In: Proc. third conference of integer programming and combinatorial optimization (IPCO) IPCO Conference 1993, pp. 479-492.
In this paper we investigate the problem of identifying a planar subgraph of maximum weight of a given edge weighted graph. In the theoretical part of the paper, the polytope of all planar subgraphs of a graph G is defined and studied. All subgraphs of a graph G, which are subdivisions of K5 or K3,3, turn out to define facets of this polytope. We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision of K5 or K3,3. These structures give us inequalities which are used as cutting planes.
|Item Type:||Proceedings article|
|Citations:||32 (Google Scholar) ||
|Uncontrolled Keywords:||branch-and-cut facets graph drawing maximum planar subgraph planarization planar subgraph polytope polyhedral combinatorics|
|Divisions:||Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger|
|Depositing User:||Prof. Dr. Michael Jünger|
|Date Deposited:||27 Jun 2003 00:00|
|Last Modified:||01 Jul 2014 12:39|