The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related Problems
Jünger, Michael and Mutzel, Petra
(1995)
The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related Problems.
Published In:
Graph drawing : DIMACS international workshop, GD '94, Princeton, New Jersey, USA, October 10 - 12, 1994 ; proceedings, Lecture notes in computer science. 894 Springer 1995, pp. 119-130.
Abstract
In Michael Jünger and Petra Mutzel [Algorithmica, 16 (1996)] we used a branch-and-cut 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 3-connectivity, resp. degree-constraints, 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 k-connected planar graph. 3. Find a maximum planar k-connected subgraph of a given k-connected graph. 4. Given a graph G, which is not necessarily planar and not necessarily k-connected, determine a new graph H by removing r edges and adding a edges such that the new graph H is planar, spanning, k-connected, 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 k-connected subgraph polytope M. Stoer [LNCS 1531 (1992)] and the degree-constrained subgraph polytope. We point out why we are confident that a branch-and-cut algorithm for the new problem will be an implementable and useful tool in automatic graph drawing.
Download: |
Postscript
- Preprinted Version
Download (161kB) | Preview |
---|---|
Editorial actions: | View Item (Login required) |
Item Type: | Proceedings article |
---|---|
Citations: | 13 (Google Scholar) | |
Uncontrolled Keywords: | biconnectivity branch-and-cut graph drawing planar augmentation planarization polyhedral combinatorics |
Subjects: | |
Divisions: | Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger |
Related URLs: |
ZAIK Number: | zpr94-165 |
---|---|
Depositing User: | Prof. Dr. Michael Jünger |
Date Deposited: | 27 Jun 2003 00:00 |
Last Modified: | 19 Dec 2011 09:45 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/165 |