Solving the Maximum Weight Planar Subgraph Problem by Branch-and-Cut

Jünger, Michael and Mutzel, Petra (1993) 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.

Download: [img] Postscript - Preprinted Version
Download (371kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr93-128
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 01 Jul 2014 12:39