Improved Approximation of Maximun Planar Subgraph

Author:Zelikovsky, Alexander, Department of Computer ScienceUniversity of Virginia

The maximum planar subgraph problem (MPSP) asks for a planar subgraph of a given graph with the maximum total cost. We suggest a new approximation algorithm for the weighted MPSP. We show that it has performance ratio of 5/12 in the case of graphs where the maxumum cost of an edge is at most twice the minimum cost of an edge. For the variant of MPSP that asks for an outerplanar graph, the algorithm suggested is the first with the higher performance ratio (7/12 instead of 1/2).

All rights reserved (no additional license for public reuse)
Source Citation:

Zelikovsky, Alexander. "Improved Approximation of Maximun Planar Subgraph." University of Virginia Dept. of Computer Science Tech Report (1996).

University of Virginia, Department of Computer Science
Published Date: