# MPI-I-98-1-029

## Optimizing over all combinatorial embeddings of a planar graph

### Mutzel, Petra and Weiskircher, RenĂ©

**MPI-I-98-1-029**. December** **1998, 23 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 401 KBytes; 1032 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1998-1-029

**BibTeX**
`@TECHREPORT{``MutzelWeiskircher98``,`

` AUTHOR = {Mutzel, Petra and Weiskircher, Ren{\'e}},`

` TITLE = {Optimizing over all combinatorial embeddings of a planar graph},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-98-1-029},`

` MONTH = {December},`

` YEAR = {1998},`

` ISSN = {0946-011X},`

`}`