Information Technology Reference
In-Depth Information
as straight line segments they do not cross. Topologically, the circle and the half-
plane are equivalent, so a graph is outerplanar if and only if it has a crossing-free
1-page drawing. For incorporating a test of outerplanarity into methods using
Courcelle's theorem, it is convenient to use a standard characterization of the
outerplanar graphs by forbidden minors:
Lemma 3 (Chartrand and Harary [7]).
A graph G is outerplanar (
1
-page
planar) if and only if it contains neither K
4
nor K
2
,
3
as a minor.
Lemma 4 (Corollary 1.15 in [10]).
Given any fixed graph H there exists a
MSO
2
-formula ˆ such that, for all graphs G, G
|
=
ˆ if and only if G contains
H as a minor. We will write
minor
H
for ˆ.
Let
outerplanar
be the formula
¬
minor
K
4
∧¬
minor
K
2
,
3
. Then Lemma 3
implies that, for all graphs
G
,
G
if and only if
G
is outerplanar.
Because outerplanar graphs have bounded treewidth (at most two), Courcelle's
theorem together with Lemma 4 guarantee the existence of a linear time algo-
rithm for testing outerplanarity. There are of course much simpler linear time
algorithms for testing outerplanarity [18,25].
|
=
outerplanar
Crossings vs Treewidth.
Next, we relate the natural parameter for 1-page crossing
minimization (the number of crossings) to the parameter for Courcelle's theo-
rem (the treewidth). This relation will allow us to construct a fixed-parameter-
tractable algorithm for the natural parameter.
Lemma 5.
Every graph G has treewidth O
(
cr
1
(
G
))
.
See the full version of this paper (
arXiv:1408.6321)
for the proof.
Logical Characterization.
Let
G
be a graph with bounded 1-page crossing num-
ber, and consider a drawing of
G
achieving this crossing number. Then the set
of crossing edges of the drawing partitions the halfplane into an arrangement
of curves, and we can partition
G
itself into the subgraphs that lie within each
face of this arrangement. Each of these subgraphs is itself outerplanar, because
it lies within a subset of the halfplane (with its vertices on the boundary of the
subset) and has no more crossing edges; see Figure 1. This intuitive idea forms
the basis for the following characterization of the 1-page crossing number, which
we will use to construct an MSO
2
-formula for the property of having a drawing
with low crossing number.
Lemma 6.
A graph G
=(
V,E
)
has
cr
1
(
G
)
≤
k if and only if there exist edges
with
=
O
(
k
)
,
and a partition U
0
,...,U
of V \ W into (possibly empty) subsets, satisfying the
following properties:
F
=
{
e
0
,...,e
r
}
with r
=
O
(
k
)
, vertices W
=
{
v
0
,...,v
}
1. W is the set of vertices incident to edges in F.
2. F contains all edges in the induced subgraph on W.
3. There are no edges between U
i
and U
j
for i
=
j.
