Universität zu Köln

Jünger, Michael and Mutzel, Petra ORCID: 0000-0001-7621-971X (1996). Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools. Springer. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr93-145.pdf Download (330kB) | Preview

Abstract

In automatic graph drawing a given graph has to be layed-out in the plane, usually according to a number of topological and aesthetic constraints. Nice drawings for sparse nonplanar graphs can be achieved by determining a maximum planar subgraph and augmenting an embedding of this graph. This approach appears to be of limited value in practice, because the maximum planar subgraph problem is NP-hard. We attack the maximum planar subgraph problem with a branch-and-cut technique which gives us quite good and in many cases provably optimum solutions for sparse graphs and very dense graphs. In the theoretical part of the paper, the polytope of all planar subgraphs of a graph G is defined and studied. All subgraphs of a graph G, which are subdivisions of K5 or K3,3, turn out to define facets of this polytope. For cliques contained in G, the Euler inequalities turn out to be facet-defining for the planar subgraph polytope. Moreover we introduce the subdivision inequalities, V2k inequalities and flower inequalities all of which are facet-defining for the polytope. Furthermore, the composition of inequalities by 2-sums is investigated. We also present computational experience with a branch-and-cut algorithm for the above problem. Our approach is based on an algorithm which searches for forbidden substructures in a graph that contains a subdivision of K5 or K3,3. These structures give us inequalities which are used as cutting planes. Finally, we try to convince the reader that the computation of maximum planar subgraphs is indeed a practical tool for finding nice embeddings by applying this method to graphs taken from the literature.

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-546809
Journal or Publication Title:	Algorithmica
Volume:	16
Number:	1
Page Range:	pp. 33-59
Date:	1996
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/54680