Information Technology Reference
In-Depth Information
transformation of Lemma 7 to produce the formula
ʸ
4
(
U
i
,v
i
,v
j
), expressing the
outerplanarity of the induced graph on
U
i
∪{
with
v
i
and
v
j
identified.
Lemma 2 tells us that there are 2
O
(
k
2
)
ways of satisfying Property 5 of Lemma 6.
Foreachcrossingdiagram
D
with
k
crossingswecanconstructaformula
ʱ
D
(
v
0
,...,
v
,e
0
,...,e
r
) specifying that the vertices
v
0
,...,v
and edges
e
0
,...,e
r
are in con-
figuration
D
.Wethenconstructtheformula
v
i
,v
j
}
ʲ
D
≡
(
∃
v
0
,...v
)(
∃
e
0
,...,e
r
)(
∃
U
0
,...,U
)
ʱ
D
(
v
0
,...,v
,e
0
,...,e
r
)
∧
U
i
=
V \{v
0
,...,v
}∧
U
i
∩ U
j
=
∅
0
i
=
j
∧
ʸ
1
(
v
0
,...,v
;
e
0
,...,e
r
)
∧
ʸ
2
(
e
0
,...,e
r
;
v
0
,...,v
)
ʸ
4
(
U
i
,v
i
,v
i
+1
)
∧
ʸ
3
(
U
i
,U
j
)
∧
i
=0
i
=
j
of length
O
(
k
2
). This formula expresses the property that, in the given graph
G
,
we can construct a crossing diagram of type
D
, and a corresponding partition of
the vertices into subsets
U
i
, that obeys Properties 1-4 of Lemma 6. By Lemma 6,
this is equivalent to the property that
G
has a 1-page drawing with
k
crossings
in configuration
D
. Finally, we construct
onepage
k
by taking the disjunction
of the
ʲ
D
where
D
ranges over all crossing diagrams with
k
crossings. Thus,
onepage
k
is a formula of length 2
O
(
k
2
)
, expressing the property that cr
1
(
G
)
≤
≤
k
.
Theorem 1.
There exists a computable function f such that
cr
1
(
G
)
can be com-
puted in O
(
f
(
k
)
n
)
time for a graph G with n vertices and with k
=cr
1
(
G
)
.
Proof.
We have shown the existence of a formula
onepage
k
such that a graph
G
k
. By Lemma 5, the treewidth of any
graph with crossing number
k
is
O
(
k
). Applying Courcelle's theorem with the
formula
onepage
k
and the
O
(
k
) treewidth bound, it follows that computing
cr
1
(
G
) is fixed-parameter tractable in
k
.
|
=
onepage
k
if and only if cr
1
(
G
)
≤
42-p geP an y
A classical characterization of the graphs with planar 2-page drawings is that
they are exactly the subhamiltonian planar graphs:
Lemma 8 (Bernhart and Kainen [4]).
A graph is
2
-page planar if and only
if it is the subgraph of planar Hamiltonian graph.
However, this characterization does not directly help us to construct an MSO
2
-
formula expressing the 2-page planarity of a graph, as we do not know how to
construct a formula that asserts the existence of a supergraph with the given
property. Hamiltonicity and planarity are both straightforward to express in
MSO
2
, but there is no obvious way to describe a set of edges that may be of