# Item

ITEM ACTIONSEXPORT

Released

Report

#### Optimizing over all combinatorial embeddings of a planar graph

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

1998-1-029

(Any fulltext), 11KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Mutzel, P., & Weiskircher, R.(1998). *Optimizing over all
combinatorial embeddings of a planar graph* (MPI-I-1998-1-029). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-7B66-A

##### Abstract

Optimizng Over All Combinatorial Embeddings of a Planar Graph".
We study the problem of optimizing over the set of all combinatorial
embeddings of a given planar graph. Our objective function prefers certain
cycles of $G$ as face cycles in the embedding. The motivation for studying
this problem arises in graph drawing, where the chosen embedding has an
important influence on the aesthetics of the drawing.
We characterize the set of all possible embeddings of a given biconnected
planar graph $G$ by means of a system of linear inequalities with
${0,1}$-variables corresponding to the set of those cycles in $G$ which can
appear in a combinatorial embedding. This system of linear inequalities can be
constructed recursively using the data structure of SPQR-trees and a new
splitting operation.
Our computational results on two benchmark sets of graphs are surprising: The
number of variables and constraints seems to grow only linearly with the size
of the graphs although the number of embeddings grows exponentially. For all
tested graphs (up to 500 vertices) and linear objective functions, the
resulting integer linear programs could be generated within 600 seconds and
solved within two seconds on a Sun Enterprise 10000 using CPLEX.