Information Technology Reference
In-Depth Information
(
iii
) Finally, we show that testing whether a graph admits a fan-planar drawing in the
variable embedding setting is NP-complete (Sec. 5).
Preliminaries are in Sec. 2. Open problems can be found in Sec. 6. For space reasons
some proofs are sketched or omitted.
2
Preliminary Definitions and Results
A
drawing
ʓ
of a graph
G
maps each vertex to a distinct point of the plane and each
edge to a simple Jordan arc between the points corresponding to the end-vertices of the
edge. For a subgraph
G
of
G
, we denote by
ʓ
[
G
] the restriction of
ʓ
to
G
.Throughout
the paper we consider only
simple graphs
, i.e., graphs with neither multiple edges nor
self-loops; also we only consider
simple drawings
, i.e., drawingssuch that the arcs
representing two edges have at most one point in common, which is either a common
end-vertex or a common interior point where the two arcs properly cross each other.
For each vertex
v
of
G
,thesetofedges incident to
v
is called the
fan of
v
. Clearly,
each edge (
u,v
) of
G
belongstothefanof
u
andtothefanof
v
at the same time. Two
edges that do not share a vertex are called
independentedges
; two independent edges
always belong to distinct fans. A
fan-planardrawing
ʓ
of
G
,isadrawing of
G
such
that: (
a
) no edge is crossed by two independent edges; (
b
) there are not two adjacent
edges (
u,v
), (
u,w
) that cross an edge
e
from different “sides” while moving from
u
to
v
and from
u
to
w
. The forbidden configurations (
a
) and (
b
) are depicted in Fig.2(a)
and Fig. 2(b), respectively. Figures 2(c) and 2(d) show two allowed configurations of a
fan-planar drawing.A
fan-planar graph
is a graph that admits a fan-planar drawing.
u
w
x
y
v
(a)
(b)
(c)
(d)
Fig. 2.
(a)-(b) Forbidden configurations in a fan-planar drawing: (c)-(d) Allowed configurations
in a fan-planar drawing
The next property immediately follows from the definition of fan-planar drawings.
Property 1.
A fan-planar drawing does not contain 3-mutually crossing edges.
Let
ʓ
be a non-planar drawing of
G
;the
planarenhancement
ʓ
of
ʓ
is the drawing
obtained from
ʓ
by replacing each crossing point with a dummy vertex. The boundary
of each face
f
of
ʓ
consists of a sequence of real and dummy vertices; the connected
region
f
of the plane that corresponds to
f
in
ʓ
consists of a sequence of vertices and
crossing points. For simplicity we call
f
a
face
of
ʓ
.The
outer face
of
ʓ
is the face
corresponding to the outer face of
ʓ
. A fan-planar drawing of
G
with all vertices on the
