Information Technology Reference
In-Depth Information
V
2
=
the two independent sets of vertices of
G
.Suppose that in
ʓ
v
i
precedes
v
i
+1
along the layer of
V
1
(for
i
=1
,...,n
1
−
{
v
n
1
+1
,...,v
n
}
1), and
v
j
precedes
v
j
+1
along the layer of
V
2
(for
j
=
n
1
+1
,...,n
1). Construct from
G
asuper-graph
G
∗
, by adding an edge (
v
i
,v
i
+1
),for
i
=1
,...,n
1
−
−
1, and an edge (
v
j
,v
j
+1
),for
j
=
n
1
+1
,...,n
.Graph
G
∗
is still outer fan-planar. Moreover, since
G
does not
contain a
K
5
subgraph (because it is bipartite), also
G
∗
does not contain a
K
5
subgraph,
as otherwise at least three vertices of the same layer in
G
should form a 3-cycle in
G
∗
(which does not happen by construction). Thus, by Lemma 3 and Property 1, the
crossinggraph of any outer fan-planar drawing of
G
∗
contains only even cycles. Hence,
denoted as
m
∗
the number of edges of
G
∗
, by Lemma 2 we have
m
∗
≤
3
n
−
6,and
therefore
m
=
m
∗
−
(
n
−
2)
≤
2
n
−
4. A family of 2-layer fan-planar graphs with
2
n
−
4 edges (for
n
≥
3) are the complete bipartite graphs
K
2
,n−
2
.
4
Fan-Planar and
k
-planar Graphs
A
k
-planardrawing
is a drawing where each edge is crossed at most
k
times, and
a
k
-planar graph
is a graph that admits a
k
-planar drawing. Clearly, every 1-planar
graph is also a fan-planar graph. Also, both the maximumnumber of edges of fan-
planar graphs [28] and the maximumnumber of edges of 2-planar graphs [30] have
been shown to be 5
n
10.Thusitisnatural to ask what is the relationship between fan-
planar and 2-planar graphs. More in general, we prove that there are fan-planar graphs
that are not
k
-planar, for any
k
−
1, and that there are
k
-planar graphs (for
k>
1)that
are not fan-planar. The existence of fan-planar graphs that are not
k
-planar is proved
with a counting argument on the minimumnumber of crossingsofgraph drawings.
The
crossing number
cr
(
G
) of
G
is the smallest number of crossingsrequired in any
drawing of
G
.Wegive the following.
≥
Theorem 3.
Fo r any integer
k
≥
1
there is agraph thatisfan-planarbut not
k
-planar.
Proof.
Consider the complete 3-partite graph
K
1
,
3
,h
.Thisgraph is fan-planar for every
h
1 (see Fig.5(a)).Itisknownthat
cr
(
K
1
,
3
,h
)=2
2
h−
2
+
2
[7,31]. For
≥
h
=4
k
+2,wehave
cr
(
K
1
,
3
,
4
k
+2
)=2
4
k
+
2
4
k
+
2
+
4
k
+
2
=4
k
(2
k
+1)+2
k
+
1=8
k
2
+6
k
+1.Thus, in every drawing of
K
1
,
3
,
4
k
+2
there are at least 8
k
2
+6
k
+1
crossings. On the other hand, in a
k
-planar drawing there can be at most
k
2
crossings,
where
m
is the number of edges in the drawing.Since
K
1
,
3
,
4
k
+2
has 16
k
+11edges,
to be
k
-planar it should admit a drawing with at most
k
2
=
k
(16
k
+11)
2
=8
k
2
+
1
2
k
crossings. Since 6
k
+1
>
1
2
k
for every
k
≥
1,
K
1
,
3
,
4
k
+2
is not
k
-planar.
To prove that for any
k>
1 there are
k
-planar graphs that are not fan-planar (Theo-
rem 4), we first give a technical result (Lemma 7), which will be also reused in Sec. 5.
Let
ʓ
be a fan-planar drawing of a graph. We may regard crossed edges of
ʓ
as com-
posed by
fragments
, where a fragment is the portion of the edge that is between two
consecutive crossings or between one of the two end-vertices of the edgeandthefirst
crossing encountered while moving along the edge towards the other end-vertex. An
edge that is not crossed does not have any fragment. Figure 5(b) shows a fan-planar
drawing of the
K
7
graph and Fig. 5(c) shows the fragments of the drawing in Fig.5(b).
