Information Technology Reference
In-Depth Information
Proof.
We prove the statement by using areduction from 3-P
ARTITION
(3P). An in-
stance of 3P is a multi-set
A
=
of 3
m
positive integers in the range
(
B/
4
,B/
2),where
B
is an integer such that
3
m
{
a
1
,a
2
,...,a
3
m
}
i
=1
a
i
=
mB
.3P asks whether
A
can
be partitioned into
m
subsets
A
1
,A
2
,...,A
m
, each of cardinality 3,such that the sum
of the numbers in each subset is
B
.As3P is
strongly
NP-hard [13], it is not restrictive
to assume that
B
is bounded by a polynomial in
m
.
Before describing our transformation, we need to introduce the concept of
barrier
gadget
.An
n
-vertex
barrier gadget
is a graph consisting of a cycle of
n
5 vertices
plus all its 2-hop edges; a barrier gadget is therefore a maximal outer-2-planar graph.
We m a ke use of barrier gadgets in order to constraint the routes of some specific paths
of
G
A
. Indeed, in a fan-planar drawing of a biconnected graph containing an outer-2-
planar drawing
ʓ
b
of a barrier gadget, no path can enter inside the boundary cycle of
ʓ
b
and cross a 2-hop edge. Also, if a path enters in
ʓ
b
without crossing any 2-hop edge,
then it must immediately exit from
ʓ
b
forming a fan-crossing with an outer edgeof
ʓ
b
.
Now, we are ready to describe how to transform an instance
A
of 3P into an instance
≥
of FP-FRS. We start from the construction of graph
G
A
which will be al-
ways biconnected. First of all, we create a
globalring barrier
by attaching four barrier
gadgets
G
t
,
G
r
,
G
b
and
G
l
as depicted in Fig.4.
G
t
is called the
top beam
and contains
exactly 3
mK
vertices, where
K
=
G
A
,
R
A
+1.
G
r
is the
right wall
and has only five
vertices.
G
b
and
G
r
are called the
bottom beam
and the
left wall
, respectively, and they
are defined in a specular way. Observe that
G
t
,
G
r
,
G
b
and
G
l
can be embedded so that
all their vertices are linkable to points within the closed region delimited by the global
ring barrier. Then, we connect the top and bottom beams by a set of 3
m
columns
,see
Fig. 4 for an illustration of the case
m
=3. Each
column
consists of a stack of 2
m
B/
2
1
cells
;a
cell
consists of a set of pairwise disjoint edges, called the
verticaledges
of
that cell. In particular, there are
m
−
−
1
bottommost cells
, one
central cell
and
m
−
1
topmost cells
. Cells of a same column are separated by 2
m
2 barrier gadgets, called
floors
. Central cells (that are 3
m
in total) have a number of vertical edges depending on
the elements of
A
. Precisely, the central cell
C
i
of the
i
-th column contains
a
i
vertical
edges connecting its delimiting floors (
i
−
). Instead, all the remaining
cells have, each one,
K
vertical edges. Hence, a non-central cell contains more edges
than any central cell. Further, the number of vertices of a floor is given by the number
of its incident vertical edges minustwo.Let
u
and
v
be the “central” vertices of the left
and right walls, respectively (see also Fig. 4). We conclude the construction of graph
G
A
by connecting vertices
u
and
v
with
m
pairwise internally disjoint paths, called the
transversalpaths
of
G
A
; each transversal path has exactly (3
m
∈{
1
,
2
, ...,
3
m
}
−
3)
K
+
B
edges.
R
A
, we define a cyclic order of edges
around each vertex that is compatible with the one depicted in Fig. 4. From what said,
it is straightforward to see that an instance of 3P can be transformed into an instance of
FP-FRS in polynomial time in
m
.
Let
A
be a
Ye s
-instance of 3P, we show that
Concerning the choice of a rotation system
G
A
,
R
A
admits a fan-planar drawing
ʓ
A
preserving
R
A
. We observe that such a drawing is easy to compute if one omits
all the transversal paths. It is essentially a drawing like that one depicted in Fig.4,
where columns are one next to the other within the closed region delimited by the
global ring barrier. However, by exploiting asolution
{
A
1
,A
2
,...,A
m
}
of 3P for the