Information Technology Reference
In-Depth Information
v
10
u
1
u
7
v
10
v
10
v
1
v
9
v
1
v
9
v
1
v
9
K
7
v
2
v
2
v
2
v
8
v
8
v
8
v
3
v
3
v
3
v
7
v
7
v
7
v
4
v
6
v
4
v
6
v
4
v
6
v
5
v
5
v
5
(a)
(b)
(c)
Fig. 6.
(a)-(c) Illustration for the proof of Theorem 4: (a) the graph
G
;(b)thegraph
G
;(c)the
graph
G
Proof.
Similarly to [34], a non-deterministic algorithm to test if a graph admits a fan-
planar drawing with
k
crossings considers all possible
k
pairs of edges that cross (and
the order of the crossingsalong the edges), discards the configurations where an edge
crosses more than one fan, replaces crossings with dummy vertices, and tests the ob-
tained graph for planarity. Then the problem belongstoNP.
We now prove the hardness. Given an instance
G
=(
V,E
) of the 1-planarity
testing we build an instance
G
f
=(
V
f
,E
f
) of the fan-planarity testing by replac-
ing each edge (
u,v
)
E
with two
K
7
graphs with vertices
u
=
u
1
,u
2
,...,u
7
and
v
=
v
1
,v
2
,...,v
7
, called
attachment gadgets
and joined by a
spanning
edge (
u
7
,v
7
)
(see Fig. 7 for an illustration).
G
f
=(
V
f
,E
f
) can be constructed in polynomial time,
having
∈
|
V
f
|
=
|
V
|
+
|
E
|×
12 vertices and
|
E
f
|
=
|
E
|×
43 edges, where
|
E
|×
42
of them belong to the attachment gadgets and the remaining
are spanning edges
that join different attachment gadgets. We show that
G
is 1-planar if and only if
G
f
is
fan-planar. If
G
admits a 1-planar drawing, replace each edge (
u,v
) of
G
with two fan-
planar drawingsof
K
7
like those depicted in Fig. 5(b) and with edge (
u
7
,v
7
),insuch a
way that the possible crossing of (
u,v
) occurs on (
u
7
,v
7
). The obtained drawing of
G
f
is fan-planar since each attachment gadget has a fan-planar drawing and each spanning
edge has at most one crossing.Conversely,suppose
G
f
admits a fan-planar drawing
ʓ
f
. By Lemma 7, for any attachment gadget of
G
f
attached to vertex
u
, there is at least
asequence of fragments leading from
u
=
u
1
to
u
7
. As in the proof of Theorem 4,
call such a sequence of fragments the
spine
of the attachment gadget. Delete from
ʓ
f
all fragments except those in the spines. Delete from
ʓ
f
all uncrossed edges except the
spanning edges. Remove also isolated vertices. A drawing
ʓ
of
G
is obtained, where
the drawing of edge (
u,v
) is given by the spine from
u
=
u
1
to
u
7
, the spanning edge
(
u
7
,v
7
), and the spine from
v
7
to
v
1
=
v
. Observe that,
u
|
E
|
=
v
, as otherwise there
would be a self-loop in
G
. We claim that
ʓ
is a 1-planar drawing of
G
. Indeed, frag-
ments in the spines can not be crossed by any other fragment or spanning edgeof
ʓ
f
.
It follows that spanning edges can cross only among themselves in
ʓ
f
.However,they
can cross only once, as they are a matching of
G
f
and
ʓ
f
is fan-planar. Hence,
ʓ
is a
1-planar drawing,but not necessarily simple; indeed, it may happen that two crossing
edges (
u,v
) and (
w,z
) in
ʓ
share an end-vertex, say
u
=
w
(this happens when in
ʓ
f
there are two crossing spanning edges of two
K
7
attached to
u
). The crossing between
(
u,v
) and (
u,z
) in
ʓ
can be easily removed by rerouting the edges (see Fig.7(c)).
