Information Technology Reference
In-Depth Information
more than constant size, is not a subset of the existing edges, and can be used
to augment the given graph to form a planar Hamiltonian graph.
For this reason we provide a new characterization, which we model on a stan-
dard characterization of planar graphs: a graph is planar if and only if, for every
cycle
C
, the flaps of
C
can be partitioned into two subsets (the interior and
exterior of
C
) such that no two flaps in the same subset cross each other. For
instance, this characterization has been used as the basis for a cubic-time divide
and conquer algorithm for planarity testing, which recursively subdivides the
graph into cycles and non-crossing subsets of flaps [2,14,23]. In our characteriza-
tion of 2-page graphs, we apply this idea to a special set of cycles, the boundaries
of maximal regions within each halfplane that are separated from the spine of a
2-page book embedding by the edges of the embedding. The cycles of this type
are edge-disjoint, and if a single cycle of this type has been identified then its
interior flaps can also be identified easily: each interior flap is a single edge, and
an edge forms an interior flap if and only if it belongs to the same page as the
cycle in the topic embedding and has both its endpoints on the cycle. As well
as identifying which of the two pages each edge of a given graph is assigned
to, our MSO
2
formula will partition the edges into three different types of edge:
the ones that belong to these special cycles, the ones that form interior flaps
of these special cycles, and the remaining
isthmus
edges that, if deleted, would
disconnect parts of their page.
Suppose we are given a graph
G
=(
V,E
) and a partition of its edges into two
subsets
A, B
, intended to represent the two pages of a 2-page drawing of
G
.We
define the graph separate(
G
;
A, B
) that splits each vertex of
G
into two vertices,
one in each page, with a new edge connecting them. Thus, separate(
G
;
A, B
)has
2
n
vertices, which can be labeled by pairs of the form (
v,X
)where
v
is a vertex
in
V
and
X
is one of the two sets in
A, B
. It has an edge between (
x, X
)and
(
y,Y
) if either of two conditions is met: (1)
x
=
y
and
X
=
Y
,or(2)
X
=
Y
and there is an edge between
x
and
y
in
X
.
Lemma 9.
A graph G
=(
V,E
)
is
2
-page planar if and only if there exists a
partition A
b
, A
c
, A
i
, B
b
, B
c
, B
i
of E into six subsets such that, for each of the
two choices of X
=
A and X
=
B, these subsets satisfy the following properties:
1. X
c
is a union of edge-disjoint cycles.
2. X
c
∪
X
b
does not contain any additional cycles that involve edges in X
b
.
3. For every edge e in X
i
there exists a cycle in X
c
containing both endpoints
of e.
4. The graph formed by the edges X
i
∪
X
b
is outerplanar.
5. For each cycle C in X
c
it is not possible to find two vertex-disjoint paths
P
1
and P
2
in E such that neither path is a single edge in X
i
,allfourpath
endpoints are distinct vertices of C, neither path contains a vertex of C in its
interior, and the two pairs of path endpoints are in crossing position on C.
6. The subdivision
separate(
G
;
A
b
∪
X
c
∪
A
c
∪
A
i
,B
b
∪
B
c
∪
B
i
)
is planar.
Figure 2 illustrates the division of edge into six subsets described in Lemma 9.
For the proof of Lemma 9, see the full version of this paper.
