The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related ProblemsJü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. 119130(Official URL: http://dx.doi.org/10.1007/3540589503_363). This is the latest version of this item.
Official URL: http://dx.doi.org/10.1007/3540589503_363
AbstractIn [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 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 \mathbb{N}. (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 [JM93], the kconnected subgraph polytope [S92] and the degreeconstrained 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.
Available Versions of this Item
Actions (login required)
