Information Technology Reference
In-Depth Information
The next lemma claims that odd cycles in the crossinggraph correspond to
K
5
(the
proof uses similar arguments as the proof of Lemma 3.
Lemma 4.
Let
G
be amaximally dense outer fan-planar graphandlet
ʓ
be an outer
fan-planardrawing of
G
.If
CR(
ʓ
)
contains a cycle
C
of length
5
,then thesubgraph
of
G
induced by theend-vertices of theedges corresponding to the vertices of
C
is
K
5
.
We now prove the upper bound on the density of outer fan-planar graphs.
Lemma 5.
Let
G
be amaximally dense outer fan-planar graphwith
n
vertices and
m
edges. Then
m
≤
3
n
−
5
edges.
Proof.
Let
ʓ
be an outer fan-planar drawing of
G
. We first claim that
G
is biconnected.
Suppose by contradiction that
G
is not biconnected, and let
C
1
and
C
2
be two distinct
biconnected components of
G
that share a cut-vertex
v
.Let
u
be the first vertex of
G
encountered while moving from
v
clockwise on the external boundary of
ʓ
[
C
1
],and
let
w
be the first vertex encountered while moving from
v
counterclockwise on the
external boundary of
ʓ
[
C
2
]. One can suitably add edge (
u,w
) in
ʓ
, still getting an
outer fan-planar drawing, which contradicts the hypothesis that
G
is maximally dense.
Now, by Corollary 1, CR(
ʓ
) can only have either even cycles or cycles of length 5.
Also, by Lemma 4, every cycle of length 5 in CR(
ʓ
) corresponds to a subset of edges
whose end-vertices induce
K
5
. We prove the statement by induction on the number
h
of
K
5
subgraphs in
G
.
Base Case.
If
h
=0then, by Lemma 2,
G
has at most 3
n
6 edges.
InductiveCase.
Suppose by induction that the claim is truefor
h
−
0,andsuppose
G
contains
h
+1subgraphs that are
K
5
.Let
G
∗
be one of these
h
+1subgraphs.
Let
e
=(
u,v
) be an edgeontheouter face of
ʓ
[
G
∗
] that is not on the outer face of
ʓ
.
Vertices
u
and
v
are a separation pair of
G
, otherwise there would be a vertex of
G
that is
not on the outer face of
ʓ
, which is impossible because
ʓ
is an outer fan-planar drawing
by hypothesis. Hence, we can split
G
into two biconnected subgraphs that share only
edge
e
, one of them containing
G
∗
.Let
G
1
,G
2
,...,G
k
(
k
≥
≤
5) be the biconnected
subgraphs of
G
distinct from
G
∗
such that each
G
i
shares exactly one edge with
G
∗
.
Each
G
i
(
i
=1
,
2
,...,k
) contains at most
h
subgraphs that are
K
5
, and therefore it has
at most 3
n
i
−
5 edges by induction, where
n
i
denotes the number of vertices of
G
i
.On
the other hand,
G
∗
has 3
n
∗
−
5=10edges, where
n
∗
=5is the number of vertices
of
G
∗
. It follows that
m
3(
n
∗
+
n
1
+
≤
···
+
n
k
)
−
5(
k
+1)
−
k
(
k
≤
5). Since
n
∗
+
n
1
+
···
+
n
k
≤
n
+2
k
we have
m
≤
3(
n
+2
k
)
−
5(
k
+1)
−
k
=3
n
−
5.
The existence of an infinite family of outer fan-planar graphs that match the 3
n
−
5
bound is proved in the next lemma. Refer to Fig. 4 for an illustration.
Lemma 6.
Fo r any integer
h
≥
1
there exists an outer fan-planar graph
G
with
n
=
3
h
+2
vertices and
m
=3
n
−
5
edges.
Proof.
Consider
h
graphs
X
1
,...,X
h
,such that each
X
i
is a
K
5
graph, for
i
=
1
,...,h
. We now describe how to construct
G
. The idea is to “glue”
X
1
,...,X
h
to-
gether in such a way that they share single edges one to another. The proof is by induc-
tiononthenumber of merged graphs. Denote by
G
i
the graph obtained after merging