Information Technology Reference
In-Depth Information
outer face is called an
outer fan-planardrawing
of
G
. Observe that the configuration in
Fig. 2(b) cannot occurinadrawing with all vertices on the outer face; hence, a drawing
is outer fan-planar if and only if all vertices are on the outer face and it does not contain
an edge crossed by two independent edges. An
outer fan-planar graph
is a graph that
admits an outer fan-planar drawing.Anouter fan-planar graph
G
is
maximal
,ifnoedge
can be added to
G
without loosing the property that
G
remains outer fan-planar. An
outer fan-planar graph
G
with
n
vertices is
maximally dense
if it has the maximum
number of edges among all outer fan-planar graphs with
n
vertices. If
G
is maximally
dense then it is also maximal, but not vice versa. The following property holds.
Lemma 1.
Let
G
=(
V,E
)
be amaximalouter fan-planar graphandlet
ʓ
be an outer
fan-planardrawing of
G
.Theouter face of
ʓ
does not contain crossing points, i.e., it
consists of
|
V
|
uncrossed edges.
Given an outer fan-planar drawing
ʓ
of a maximal outer fan-planar graph
G
,the
edges of
G
on the external boundary of
ʓ
will be also called the
outer edges
of
ʓ
.
A 2
-layer fan-planardrawing
is a fan-planar drawing such that: (
i
) each vertex is
drawn on one of two distinct horizontal lines, called
layers
; (
ii
) each edge connects
vertices of different layers and it is drawn as a vertical monotone curve. By definition,
a 2-layer fan-planar drawing is also an outer fan-planar drawing.A2
-layer fan-planar
graph
is a graph that admits a 2-layer fan planar drawing.
3
Density of Outer and 2-layer Fan-Planar Graphs
We first prove that an
n
-vertex outer fan-planar graph
G
has at most 3
n
−
5 edges. Then
we describe how to construct outer fan-planar graphs with
n
vertices and 3
n−
5 edges.
Let
G
be a graph and let
ʓ
beadrawing of
G
.The
crossing graph
of
ʓ
, denoted as
CR(
ʓ
),isagraph having a vertex for each edgeof
G
and an edge between any two
vertices whose corresponding edges cross in
ʓ
.AcycleofCR(
ʓ
) of odd length will
be called an
odd cycle
of CR(
ʓ
); similarly, an
even cycle
of CR(
ʓ
) is a cycle of even
length. In order to prove the 3
n
5 upper bound, we can assume that
G
is a maxi-
mally dense outer fan-planar graph. We start by proving some interesting combinatorial
properties of
G
related to the cycles of the crossinggraph of
G
.
−
Lemma 2.
Let
G
=(
V,E
)
be amaximalouter fan-planar graphwith
n
=
|
V
|
vertices
and
m
=
edges. Let
ʓ
be an outer fan-planardrawing of
G
.If
CR(
ʓ
)
does not
have odd cycles then
m
|
E
|
≤
3
n
−
6
.
Proof.
If CR(
ʓ
) does not contain odd cycles, then it is bipartite and its vertices can be
partitioned into two independent sets
W
1
and
W
2
. Since by Lemma 1 the outer edges of
ʓ
are not crossed, they correspond to
n
isolated vertices in CR(
ʓ
). We can arbitrarily
assign all these vertices to the same set, say
W
1
. Denote by
E
i
the set of edges of
G
corresponding to the vertices of
W
i
(
i
). Clearly,
E
1
and
E
2
partition the set
E
. Since no two edges of
E
i
cross in
ʓ
, then the two subgraphs
G
1
=(
V,E
1
) and
G
2
=(
V,E
2
) are outerplanar graphs, where
∈{
1
,
2
}
|E
1
|≤
2
n −
3 and
|E
2
|≤
2
n −
3
− n
.
Thus,
m
=
|E|
=
|E
1
|
+
|E
2
|≤
3
n −
6.
Thenextlemmashowsthatthelength of any odd cycle of CR(
ʓ
) is at most 5.
