Improved Approximation of Maximun Planar Subgraph

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

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).

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

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

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1996