Information Technology Reference
In-Depth Information
Lemma 3.
Let
G
be amaximally dense outer fan-planar graphwith
n
vertices andlet
ʓ
be an outer fan-planardrawing of
G
.
CR(
ʓ
)
does not contain odd cycles of length
greater than
5
.
Proof.
Let
C
be an odd cycle of length
in CR(
ʓ
).Let
E
(
C
)=
{e
0
=
(
u
0
,v
0
)
,...,e
−
1
=(
u
−
1
,v
−
1
)
}
be the set of
edges of
G
corresponding to
the vertices of
C
,such that
e
i
crosses
e
i
+1
for
i
=0
,...,l
1, where indices are
taken modulo
. Recall that all vertices of
G
are on the outer face of
ʓ
, which implies
that the end-vertices of the edges in
E
(
C
) are encountered in the following order when
walking clockwise on the boundary of the outer face of
ʓ
:
u
i
precedes
v
i−
1
and
v
i
precedes
u
i
+2
(see, e.g., Fig.3(a)).Furthermore, vertices
v
i
and
u
i
+2
must coincide,
for
i
=0
,...,
−
1,then
edge
e
i
+1
is crossed by two independent edges (i.e.,
e
i
and
e
i
+2
), which contradicts the
hypothesis that
ʓ
is fan-planar. See also Fig.3(a).Thus, we have that
u
i
precedes
u
i
+1
while walking clockwise on the boundary of the outer face of
ʓ
,for
i
=0
,...,
−
1. Indeed, if
v
i
and
u
i
+2
are distinct, for some
i
=0
,...,
−
1,
asshowninFig. 3(b). Moreover, it can be seen that the edges in
E
(
C
) are not crossed
by any edge not in
E
(
C
), as otherwise the drawing would not be fan-planar.
−
u
1
v
6
v
0
u
2
u
1
u
2
e
6
e
2
e
6
e
0
e
1
v
1
e
0
e
1
u
0
u
3
u
0
u
3
e
2
v
5
e
5
e
3
e
3
u
6
v
2
v
4
u
6
u
4
e
4
e
5
e
4
u
4
v
3
u
5
u
5
(a)
(b)
Fig. 3.
Illustration for the proof of Lemma 3. (a) An edgeset
E
(
C
) with
=7.If
v
3
and
u
5
do
not coincide,
e
4
(dashed) is crossed by the two independent edges
e
3
and
e
5
(in bold). (b)
E
(
C
)
with
=7,where
v
i
coincides with
u
i
+2
,for
i
=0
,...,
7.
Now, suppose by contradiction that
is odd and greater than 5 (see Fig. 3(b)). Con-
sider a vertex
u
i
,forsome
i
=0
,...,−
1, and denote by
V
the set of vertices encoun-
tered between
u
i
+3
and
u
i−
3
while walking clockwise on the boundary of the outer
face of
ʓ
(including
u
i
+3
and
u
i−
3
). Vertex
u
i
cannot be adjacent to any vertex in
V
.
Namely, if an edge
e
=(
u
i
,u
j
) existed, for some
u
j
∈
V
,thenitwould be crossed by
the two independent edges
e
i−
1
and
e
j−
1
.Thus, removing
e
i−
1
from
ʓ
, one can suit-
ably connect
u
i
to all the vertices in
V
, still obtaining a fan-planar drawing
ʓ
∗
with
n
vertices. Since the size of
V
is
7 by assumption, then
ʓ
∗
has at least two
edges more than
ʓ
, which contradicts the hypothesis that
G
is maximally dense.
−
5,and
≥
The following corollary is a consequence of Lemma 3 and Property 1.
Corollary 1.
Let
G
be amaximally dense outer fan-planar graph.Any odd cycle in the
crossing graph of a fan-planardrawing of
G
hasexactly length
5
.
