Information Technology Reference
In-Depth Information
U
1
U
2
U
0
U
3
U
4
Fig. 1.
A 1-page drawing of a
graph with two crossings and
five outerplanar subgraphs.
Fig. 2.
A 2-page planar graph with its edges parti-
tioned into the six sets
A
b
(green edges),
A
c
(blue
edges),
A
i
(red edges),
B
b
(yellow edges),
B
c
(pur-
ple edges), and
B
i
(gray edges).
4. There is an outerplanar embedding of the induced subgraph on U
i
∪{v
i
,v
i
+1
}
with v
i
and v
i
+1
adjacent for all
0
i<.
5. The edges in F produce at most k crossings when their endpoints (the vertices
in W) are placed in order according to their indices.
≤
We now construct a formula
onepage
k
, based on Lemma 6, such that
G
|
=
onepage
k
if and only if cr
1
(
G
)
onepage
k
will have the
overall form of a disjunction, over all crossing configurations, of a conjunction
of sub-formulas representing Properties 1-4 in Lemma 6. Property 5 will be
represented implicitly, by the enumeration of crossing configurations. The first
three properties are easy to express directly: the formulas
≤
k
. The formula
ʸ
1
(
W, F
)
≡
∀
v
)[
v
∈
W
ₒ
∃
e
)[
e
∈
F
∧
I
(
e,v
)]]
(
(
ʸ
2
(
F,W
)
≡
(
∀
e
)[(
∀
v
)[
I
(
e,v
)
ₒ
v
∈
W
]
ₒ
e
∈
F
]
ʸ
3
(
U
i
,U
j
)
≡¬
(
∃
e
)(
∃
u,v
)[
I
(
e,u
)
∧
I
(
e,v
)
∧
u
∈
U
i
∧
v
∈
U
j
]
express in MSO
2
Properties 1, 2, and 3 of Lemma 6 respectively.
To express Property 4 we first observe that it is equivalent to the property
that the induced subgraph on
U
i
∪{
with
v
i
and
v
i
+1
identified (merged)
to form a single supervertex is outerpalanar. That is, the requirement in Prop-
erty 4 that vertices
v
i
and
v
i
+1
be adjacent in the outerplanar embedding can be
enforced by identifying the vertices. To express this property we need the follow-
ing lemma, which can be proved in straightforward manner using the method of
syntactic interpretations. (For details on this method see [13,15].)
v
i
,v
i
+1
}
Lemma 7.
For every
MSO
2
-formula ˆ there exists an
MSO
2
-formula ˆ
∗
(
v
1
,v
2
)
such that G
=
ˆ
∗
(
a, b
)
if and only if G/a
|
∼
b
|
=
ˆ,whereG/a
∼
b is the graph
constructed from G by identifying vertices a and b.
outerplanar
by restricting its quantifiers to only quantify over vertices (and sets of vertices)
in
U
i
∪{
Now, to construct
ʸ
4
(
U
i
,v
i
,v
j
)wefirstmodifytheformula
and edges (and sets of edges) between these vertices. This mod-
ified formula describes the outerplanarity of
U
i
∪{
v
i
,v
j
}
v
i
,v
j
}
. We then apply the
