Information Technology Reference
In-Depth Information
5
5
4
6
4
6
...
1
2
3
7
1
2
3
7
(a)
(b)
(c)
Fig. 5.
(a) A fan-planar drawing of
K
1
,
3
,h
. (b) A fan-planar drawing of the
K
7
graph. (c) The
fragments of the fan-planar drawing in (b) are the thicker lines.
We consider two fragments
adjacent
if they share a common crossing or a common
end-vertex. The next lemma provides an interesting and useful property.
Lemma 7.
In any fan-planardrawing of the
K
7
graph, any pair of vertices is joined
byasequence of adjacentfragments.
Theorem 4.
Fo r any integer
k>
1
there is agraph thatis
k
-planarbut not fan-planar.
Proof sketch:
Since 2-planar graphs are also
k
-planar graphs, for
k>
1, we can prove
that there is a 2-planar graph that is not fan-planar. Let
G
be a graph consisting of a
cycle
C
=(
v
1
,v
2
,...,v
10
) and of the edges (
v
1
,v
4
), (
v
5
,v
10
), (
v
6
,v
9
) (see Fig.6(a)).
Let
G
be the graph obtained from
G
by replacing each edge (
v
i
,v
j
) (1
10)
with a copy of
K
7
, whose vertices are denoted as
u
1
,u
2
,...,u
7
,sothat
v
i
=
u
1
and
v
j
=
u
7
(see Fig.6(b)).Thecopyof
K
7
that replaces (
v
i
,v
j
) is denoted as
K
i,
7
.Let
G
be the graph obtained from
G
by adding the edges (
v
1
,v
7
), (
v
2
,v
6
), (
v
3
,v
9
), (
v
4
,v
8
)
(see Fig.6(c)).
G
is 2-planar (planarly embed
G
asshowninFig.6(a)).Construct
adrawing
ʓ
of
G
by replacing each edgeof
G
with a drawing of
K
i,
7
like that in
Fig.5(b)(seeFig. 6(b)), and draw the edges (
v
1
,v
7
), (
v
2
,v
6
), (
v
3
,v
9
), (
v
4
,v
8
) inside
C
as in Fig.6(c).
ʓ
is 2-planar. To prove that
G
is not fan-planar note that, by Lemma 7,
each
K
i,j
7
≤
i,j
≤
10) has a sequence of fragments leading from
v
i
=
u
1
to
v
j
=
u
7
,
which we call
spine
. In any fan-planar drawing of
G
, this spine cannot be crossed by
edges that do not belong to
K
i,
7
(otherwise there would be an edge crossed by two
independent edges). Thus, every
K
i,j
7
is not “traversed” by external edges, and this
forces (
v
1
,v
7
), (
v
2
,v
6
), (
v
3
,v
9
), (
v
4
,v
8
) to violate fan-planarity, as in Fig.6(c).
(1
≤
i,j
≤
5
Complexity of the Fan-Planarity Testing Problem
We exploit the results of Secs. 3 and 4 to prove that testing whether a graph is fan-
planar in the variable embedding setting is NP-complete. We call this problem the
fan-
planarity testing
.Weuse a reduction from the
1-planarity testing
,whichisNP-complete
in the variable embedding setting [25,29]. The 1-planarity testing asks whether a given
graph admits a 1-planar drawing. We prove the following.
Theorem 5.
Fan-planarity testing is NP-complete.
