Information Technology Reference
In-Depth Information
for stronger parameters, allowing
k
-page crossing minimization to be performed
in polynomial time for a much wider class of graphs.
New Results.
We design fixed-parameter algorithms for computing the minimum
number of crossings cr
1
(
G
) in a 1-page drawing of a graph
G
, and the minimum
number of crossings cr
2
(
G
) in a 2-page drawing of
G
. Ideally, fixed-parameter
algorithms for crossing minimization should be parameterized by their
natural
parameter
, the optimal number of crossings. We achieve this ideal bound, for the
first time, for cr
1
(
G
). However, for cr
2
(
G
), even testing whether a given graph is
2-page planar (that is, whether cr
2
(
G
)=0)is
NP
-complete [8]. Therefore, unless
P
, there can be no fixed-parameter-tractable algorithm parameterized by
the crossing number. Instead, we show that cr
2
(
G
) is fixed-parameter tractable
in the sum of the natural parameter and the treewidth of
G
. One consequence of
our result on cr
2
(
G
) is that it is possible to test whether a given graph is 2-page
planar, in time that is fixed-parameter tractable with respect to treewidth.
We construct these algorithms via Courcelle's theorem [9,10], which connects
the expressibility of graph properties in monadic second order logic with the
fixed-parameter tractability of these properties with respect to treewidth. Re-
call that second order logic extends first order logic by allowing the quantifi-
cation of
k
-ary relations in addition to quantification over individual elements.
In monadic second order logic we are restricted to quantification over unary re-
lations (equivalently subsets) of vertices and edges. The property of having a
2-page topic embedding is easy to express in (full) second-order logic, via the
known characterization that a graph has such an embedding if and only if it is
a subgraph of a Hamiltonian planar graph [4]. However, this expression is not
allowed in monadic second-order logic because the extra edges needed to make
the input graph Hamiltonian cannot be described by a subset of the existing
vertices and edges of the graph. Instead, we prove a new structural description
of 2-page planarity that is more easily expressed in monadic second order logic.
=
NP
Related Work.
As well as the previous work on crossing minimization for almost-
trees [3], related results in fixed-parameter optimization of crossing number in-
clude a proof by Grohe, using Courcelle's theorem, that the topological crossing
number of a graph is fixed-parameter tractable in its natural parameter [15]. This
result was later improved by Kawarabayashi and Reed [17]. Based on these re-
sults the crossing number itself was also shown to be fixed-parameter tractable;
Pelsmajer et al. showed a similar result for the odd crossing number [20]. In
layered graph drawing
,Dujmovic et al. showed that finding a drawing with
k
crossings and
h
layers is fixed-parameter tractable in the sum of these two pa-
rameters; this result depends on a bound on the pathwidth of such a drawing, a
parameter closely related to its treewidth [11].
Like many of these earlier algorithms, our algorithms have a high dependence
on their parameter, rendering them impractical. For this reason we have not
attempted an exact analysis of their complexity nor have we searched for opti-
mizations to our logical formulae that would improve this complexity.
