非表示:
キーワード:
-
要旨:
We investigate the {\em constrained crossing minimization problem} for graphs
defined as follows. Given a connected, planar graph $G=(V,E)$, a combinatorial
embedding $\Pi(G)$ of $G$, and a set of pairwise distinct edges
$F\subseteq V\times V$, find a
drawing of $G\cup F$ in the plane such that the combinatorial embedding
$\Pi(G)$ of $G$ is preserved and the number of edge crossings is minimum.
This problem arises in the context of automatic graph drawing. Here, the
so--called planarization method transforms a general graph into a planar graph
and then applies planar graph drawing methods to it.
First we show NP--hardness of this problem. Then we formulate an $|F|$--pairs
shortest walks problem on an extended dual graph, where the number of crossings
between the walks is added to the cost function. We show that this dual problem
is equivalent to our original problem. Our approach to solve the dual problem
is based on polyhedral combinatorics. We investigate an ILP--formulation and
present first computational results using a branch--and--cut algorithm based on
ABACUS.
