Jünger, Michael and Mutzel, Petra
(1993)
Maximum Planar Subgraphs and Nice Embeddings: Practical Layout Tools.
[Preprint]
Abstract
In automatic graph drawing a given graph has to be layedout 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 NPhard.
We attack the maximum planar subgraph problem with a branchandcut 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 facetdefining for the planar subgraph polytope. Moreover we introduce the subdivision inequalities, V2k inequalities and flower inequalities all of which are facetdefining for the polytope. Furthermore, the composition of inequalities by 2sums is investigated.
We also present computational experience with a branchandcut 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.
Actions (login required)

View Item 