@techreport{MutzelWeiskircher98,
TITLE = {Optimizing over all combinatorial embeddings of a planar graph},
AUTHOR = {Mutzel, Petra and Weiskircher, Ren{\'e}},
LANGUAGE = {eng},
NUMBER = {MPI-I-1998-1-029},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Saarbr{\"u}cken},
YEAR = {1998},
DATE = {1998},
ABSTRACT = {Optimizng Over All Combinatorial Embeddings of a Planar Graph".<br><br>We study the problem of optimizing over the set of all combinatorial<br>embeddings of a given planar graph. Our objective function prefers certain<br>cycles of $G$ as face cycles in the embedding. The motivation for studying<br>this problem arises in graph drawing, where the chosen embedding has an<br>important influence on the aesthetics of the drawing.<br><br>We characterize the set of all possible embeddings of a given biconnected<br>planar graph $G$ by means of a system of linear inequalities with<br>${0,1}$-variables corresponding to the set of those cycles in $G$ which can<br>appear in a combinatorial embedding. This system of linear inequalities can be<br>constructed recursively using the data structure of SPQR-trees and a new<br>splitting operation.<br><br>Our computational results on two benchmark sets of graphs are surprising: The<br>number of variables and constraints seems to grow only linearly with the size<br>of the graphs although the number of embeddings grows exponentially. For all<br>tested graphs (up to 500 vertices) and linear objective functions, the<br>resulting integer linear programs could be generated within 600 seconds and<br>solved within two seconds on a Sun Enterprise 10000 using CPLEX.},
TYPE = {Research Report / Max-Planck-Institut für Informatik},
}