Information Technology Reference
In-Depth Information
4. For every edge e in X
i
, there exists a subgraph P containing e and a cycle C
in X
c
such that P consists only of vertices of C and of degree-four vertices
introduced in the planarization, P contains at least two vertices of C,andP
includes all four edges incident to each of its planarization vertices.
5. For each two edges e and f in X
i
, the two subgraphs P
e
and P
f
satisfying
Property 4 do not each have a pair of endpoints in crossing position on the
same cycle C.
6. For each cycle C in X
c
there do not exist two paths in E, such that neither
path uses edges of X
i
or interior vertices of C, with four distinct endpoints
on C in crossing position.
7. the subdivision
separate(
G
;
A
b
∪ A
c
∪ A
i
,B
b
∪ B
c
∪ B
i
)
is planar.
=
ʶ
k
if
and only if cr
2
(
G
)=
k
. To handle the planarization process we use the following
lemma. In the lemma, the notation
G
e
1
×e
2
describes the graph obtained from a
graph
G
by deleting two edges
e
1
and
e
2
that do not share a common endpoint,
and adding a new degree-4 vertex connected to the endpoints of
e
1
and
e
2
.
Now, we construct a MSO
2
-formula
ʶ
k
basedonLemma11suchthat
G
|
Lemma 12 (Grohe [15]).
For every
MSO
2
-formula ˆ there exists an
MSO
-
formula ˆ
∗
(
x
1
,x
2
)
such that G
|
=
ˆ
∗
(
e
1
,e
2
)
if and only if G
e
1
×e
2
|
=
ˆ.
Given any MSO
2
-formula
ˆ
and crossing diagram
D
, we can repeatedly apply
the lemma above to construct a formula
ˆ
D
such that
G
=
ˆ
D
(
e
0
,...,e
r
)if
|
and only if
G
D
|
=
ˆ
. With this tool in hand it is straightforward to construct
aformula
ʳ
D
, expressing the property that, in a given graph
G
we can build
a crossing diagram with the structure of
D
, and partition the planarization
G
D
into six sets, satisfying Lemma 11. So we can define
ʶ
k
to be the disjunction of
the
ʳ
D
ranging over all 2-page crossing diagrams with
k
-crossings.
Theorem 3.
There exists a computable function f such that
cr
2
(
G
)
can be
computed in O
(
f
(
k,t
)
n
)
time for a graph G with n vertices, k
=cr
2
(
G
)
,and
t
=tw(
G
)
.
6Con lu on
We have provided new fixed-parameter algorithms for computing the crossing
numbers for 1-page and 2-page drawings of graphs with bounded treewidth. The
use of monadic second order logic and Courcelle's theorem in our solutions causes
the running times of our algorithms to have an impractically high dependence
on their parameters. We believe that it should be possible to achieve a better
dependence by directly designing dynamic programming algorithms that use
tree-decompositions of the given graphs, rather than by relying on Courcelle's
theorem to prove the existence of these algorithms. Can this dependency be
reduced to the point of producing practical algorithms? For 2-page crossing min-
imization the runtime is parameterized by both the treewidth and the crossing
number. Is 2-page crossing minimization
-hard for graphs of fixed treewidth?
We leave these questions open for future research.
NP
