Information Technology Reference
In-Depth Information
v
4
v
3
v
5
s
1
t
1
t
v
2
v
6
s
2
s
v
1
t
2
(a)
(b)
Fig. 3.
(a) In the solid graph, edge
{v
2
,v
3
}
(
{v
5
,v
6
}
) is porousaround
v
2
(
v
6
, resp.). (b) Illus-
tration of Case 2 of Theorem 2.
We s a y t h a t a n outer edge
{v
1
,v
n
}
is
porous
around
v
1
if we could add a vertex
v
between
v
1
and
v
n
and an edge
maintaining outer-fan-planarity. Note that any
edge of a simple cycle, i.e., of the skeleton of an
S
-node is porousaround any of its end
vertices. Any outer edgeofa
K
4
is porousaround any of its end vertices; see Fig.3.
We use the SPQR-tree of a biconnected graph to characterize whether it is maximal
outer-fan-planar; see [5] for a proof of this theorem.
{
v,v
2
}
Theorem 2.
Abiconnected graph is maximalouter-fan-planariffthe following hold:
1) Theskeleton of any
R
-node is maximalouter-fan-planar and has an outer-fan-
planardrawing inwhichall virtualedges are outer edges,
2) No
R
-node is adjacenttoan
R
-node or an
S
-node,
3) All
S
-nodes havedegree three,
4) All
P
-nodes havedegree three and are adjacenttoa
Q
-node, and
5) Let
G
1
and
G
2
be theskeleton of thetwo neighbors of a
P
-node other than the
Q
-node andlet
be thecommonvirtualedgeof
G
1
and
G
2
.Then
G
i
,i
=
1
,
2
must not admit an outer-fan-planardrawing with
t
i
,s,t,s
i
being consecutive
aroundthecircleand
(a)edge
{
s, t
}
{
s, t
}
is porousin both
G
1
and
G
2
aroundthesame vertex, or
(b) edge
{
t
1
,s
}
(
{
s
2
,t
}
)isreal and porous around
s
(
t
, resp.), or
(c) edge
{
s
1
,t
}
(
{
t
2
,s
}
)isreal and porous around
t
(
s
,resp.).
As the number of outer-fan-planar embeddings of a 3-connected graph is bounded by
a constant, the conditions of Thm. 2 can be tested in polynomial time. If the conditions
are fulfilled, then an outer-fan-planar drawing can be constructed in linear time.
3
Recognizing Fan-Planar Graphs with Rotation System
In this section, we study the F
AN
-P
LANARITY WITH
F
IXED
R
OTATION
S
YSTEM
prob-
lem (FP-FRS), that is, the problem of deciding whether a graph
G
=(
V,E
) with a
fixed rotation system
R
R
admits a fan-planar drawing preserving
.
Theorem 3.
F
AN
-P
LANARITY WITH
F
IXED
R
OTATION
S
YSTEM
is NP-hard.
