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. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 119-130(Official URL:

This is the latest version of this item.

Full text not available from this repository.


In [JM94] 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 \mathbb{N}. (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 [JM93], the k-connected subgraph polytope [S92] 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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-58950-3_363
Classifications: G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.840 Planarization
G Algorithms and Complexity > G.420 Crossings

Available Versions of this Item

Actions (login required)

View Item View Item