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
 
Search WWH ::




Custom Search