Information Technology Reference
In-Depth Information
Lemma 1 (Courcelle's theorem [9, 10]).
Given an integer k
0
and an
MSO
2
-formula ˆ of length , an algorithm can be constructed that takes as in-
≥
put a graph G of treewidth at most k and decides in O
f
(
k,
)
(
n
+
m
)
time
·
whether G
=
ˆ,wherethefunctionf appearing in the time bound is a computable
function of the treewidth k and formula length .
|
Combinatorial Enumeration of Crossing Diagrams.
In order to show that the
properties we study can be represented by logical formulas of finite length, we
need to bound the number of combinatorially distinct ways that a subset of
edges in a
k
-page graph drawing can cross each other.
We define a 1
-page crossing diagram
to be a placement of some points on the
circumference of a circle, together with some straight line segments connecting
the points such that each point is incident to a segment, no segment is uncrossed
and no three segments cross at the same point. Two crossing diagrams are
com-
binatorially equivalent
if they have the same numbers of points and line segments
and there exists a cyclic-order-preserving bijection of their points that takes line
segments to line segments. The
crossing number
of a 1-page crossing diagram is
the number of pairs of its line segments that cross each other.
We define a 2
-page crossing diagram
to be a 1-page crossing diagram together
with a labeling of its line segments by two colors. For a 2-page crossing diagram
we define the
crossing number
to be the total number of crossing pairs of line
segments that have the same color as each other.
Lemma 2.
There are
2
O
(
k
2
)
1-page crossing diagrams with k crossings, and
there are
2
O
(
k
2
)
2-page crossing diagrams with k crossings.
Proof.
Place 4
k
points around a circle. Then every 1-page crossing diagram with
k
or fewer crossings can be represented by choosing a subset of the points and
a set of line segments connecting a subset of pairs of the points. There are 4
k
points and 4
k
(4
k
1)
/
2 pairs of points, so 2
O
(
k
2
)
possible subsets to choose.
Similarly, every 2-page crossing diagram can be represented by a subset of the
same 4
k
points, and two disjoint subsets of pairs of points, which again can be
bounded by 2
O
(
k
2
)
.
−
Two combinatorially equivalent crossing diagrams, as defined above, may have
a topology that differs from each other, or from combinatorially equivalent dia-
grams with curved edges. This is because, for an edge with multiple crossings, the
order of the crossings along this edge may differ from one diagram to another, but
this ordering is not considered as part of the definition of combinatorial equiv-
alence. For our purposes such differences are unimportant, as we are concerned
only with the total number of crossings. So we consider two crossing diagrams to
be equivalent if they have the same crossing pairs of edges, regardless of whether
the crossings occur in the same order.
3 1-page Crossing Minimization
Outerplanarity.
Recall that a graph is
outerplanar
if there exists a placement of
its vertices on the circumference of a circle such that when its edges are drawn
