Universität zu Köln

Jünger, Michael and Mutzel, Petra ORCID: 0000-0001-7621-971X (1995). The Polyhedral Approach to the Maximum Planar Subgraph Problem: New Chances for Related Problems. Springer. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr94-165.pdf - Submitted Version Download (184kB) | Preview

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{\"u}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.

Item Type:	Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Mutzel, Petra UNSPECIFIED orcid.org/0000-0001-7621-971X UNSPECIFIED
URN:	urn:nbn:de:hbz:38-546909
Series Name:	Lecture notes in computer science
Volume:	894
Page Range:	pp. 119-130
Date:	1995
Publisher:	Springer
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54690