Jünger, Michael and Mutzel, Petra
(1994)
The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related Problems.
[Preprint]
Abstract
In Michael Jünger and Petra Mutzel [Algorithmica, 16 (1996)] we used a branchandcut algorithm in order to determine a maximum weight planar subgraph of a given graph. One of the motivations was to produce a nice drawing of a given graph by drawing the found maximum planar subgraph, and then augmenting this drawing by the removed edges. Our experiments indicate that drawing algorithms for planar graphs which require 2 or 3connectivity, resp. degreeconstraints, in addition to planarity often give ''nicer'' results. Thus we are led to the following problems:
1. Find a maximum planar subgraph with maximum degree d in IN.
2. Augment a planar graph to a kconnected planar graph.
3. Find a maximum planar kconnected subgraph of a given kconnected graph.
4. Given a graph G, which is not necessarily planar and not necessarily kconnected,
determine a new graph H by removing r edges and adding a edges such that the new graph H is planar, spanning, kconnected, each node v has degree at most D(v) and r+a is minimum.
Problems (1), (2) and (3) have been discussed in the literature, we argue that a solution to the newly defined problem (4) is most useful for our goal. For all four problems we give a polyhedral formulation by defining different linear objective functions over the same polytope which is the intersection of the planar subgraph polytope, see Michael Jünger and Petra Mutzel [Proc. IPCO3 (1993)], the kconnected subgraph polytope M. Stoer [LNCS 1531 (1992)] and the degreeconstrained subgraph polytope. We point out why we are confident that a branchandcut algorithm for the new problem will be an implementable and useful tool in automatic graph drawing.
Available Versions of this Item

The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related Problems. (deposited 17 Jul 2003)
[Currently Displayed]
Actions (login required)

View Item 