非表示:
キーワード:
-
要旨:
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.
