Information Technology Reference
In-Depth Information
Crossing Minimization for 1-page and 2-page
Drawings of Graphs with Bounded Treewidth
Michael J. Bannister and David Eppstein
Department of Computer Science, University of California, Irvine
Abstract.
We investigate crossing minimization for 1-page and 2-page
topic drawings. We show that computing the 1-page crossing number
is fixed-parameter tractable with respect to the number of crossings,
that testing 2-page planarity is fixed-parameter tractable with respect
to treewidth, and that computing the 2-page crossing number is fixed-
parameter tractable with respect to the sum of the number of crossings
and the treewidth of the input graph. We prove these results via Cour-
celle's theorem on the fixed-parameter tractability of properties express-
ible in monadic second order logic for graphs of bounded treewidth.
1 Introduction
A
k-page topic embedding
of a graph
G
is a drawing that places the vertices of
G
on a line (the
spine
of the topic) and draws each edge, without crossings, inside
one of
k
half-planes bounded by the line (the
pages
of the topic) [16,19]. In one
common drawing style, an
arc diagram
, the edges in each page are drawn as
circular arcs perpendicular to the spine [24], but the exact shape of the edges
is unimportant for the existence of topic embeddings. These embeddings can be
generalized to
k-pagebookdrawings
: as before, we place each vertex on the spine
and each edge within a single page, but with crossings allowed. The
crossing
number
of such a drawing is defined to be the sum of the numbers of crossings
within each page, and the
k-page crossing number
cr
k
(
G
) is the minimum number
of crossings in any
k
-page topic drawing [22]. In an optimal drawing, two edges
in the same page cross if and only if their endpoints form interleaved intervals on
the spine, so the problem of finding an optimal drawing may be solved by finding
a permutation of the vertices and an assignment of edges to pages minimizing
the number of pairs of edges with interleaved intervals on the same page.
As with most crossing minimization problems,
k
-page crossing minimization
is
-hard; even the simple special case of testing whether the 2-page crossing
number is zero is
NP
-complete [8]. However, it may still be possible to solve
these problems in polynomial time for restricted families of graphs and restricted
values of
k
. For instance, recently Bannister, Eppstein and Simons [3] showed the
computation of cr
1
(
G
)andcr
2
(
G
) to be fixed-parameter tractable in the almost-
tree parameter; here, a graph
G
has almost-tree parameter
k
if every biconnected
component of
G
can be reduced to a tree by removing at most
k
edges. In this
paper we improve these results by finding fixed-parameter tractable algorithms
NP
