Information Technology Reference
In-Depth Information
(a) Fan-crossing
(b) Forbidden pattern I (c) Forbidden pattern II
(d) Triangle crossing
Fig. 1.
(taken from [18]) (a) A fan-crossing. (b) Forbidden crossing pattern I: An edge cannot be
crossed by two independent edges. (c) Forbidden crossing pattern II: An edge cannot be crossed
by two edges having their common end-point on different sides of it. (d) Forbidden crossing
pattern II implies that an edge cannot be crossed by three edges forming atriangle.
On the other hand, it is accepted that edge crossingshavenegative impact on the
human understanding of a graph drawing [22] and simultaneously it is NP-complete
to find drawings with minimumnumber of edge crossings [13]. This motivated the
study of “almost planar” graphs which may contain crossingsaslong as they do not
violate some prescribed forbidden crossing patterns. Typical examples include
k
-planar
graphs [23],
k
-quasi planar graphs [2], RAC graphs [8] and fan-crossing free graphs [6].
Fan-planar graphs were recently introduced in the same context [18]. A
fan-planar
drawing
of graph
G
=(
V,E
) is a simple drawing which allows for more than one
crossing on an edge
e
E
iff the edges that cross
e
are incident to a common vertex on
the same side of
e
.Such a crossing is called
fan-crossing
.Anequivalent definition can
be stated by means of forbidden crossing patterns; see Fig.1.Agraph is
fan-planar
if
it admits a fan-planar drawing. So, the class of fan-planar graphs is in a sense the com-
plement of the class of fan-crossing free graphs [6], which simply forbid fan-crossings.
Kaufmann and Ueckerdt [18] showed that a fan-planar graph on
n
vertices cannot
have more than 5
n
∈
10 edges; a tight bound. An
outer-fan-planardrawing
is a fan-
planar drawing in which all vertices are on the outer-face. A graph is
outer-fan-planar
if it admits an outer-fan-planar drawing.Anouter-fan-planar graph is
maximalouter-
fan-planar
if adding any edge to it yields a graph that is not outer-fan-planar. Note that
the forbidden pattern II is irrelevant for outer-fan-planarity.
Our main contribution is a polynomial time algorithm for the recognition of maximal
outer-fan-planar graphs (Section 2). We also prove that the general fan-planar problem
is NP-hard, for the case where the
rotation system
(i.e., the circular order of the edges
around each vertex) is given (Section 3). Due to space restrictions, some proofs are
omitted or only sketched in the text; full proofs for all results can be found in [5].
−
Related Work.
As already stated,
k
-planar graphs [23],
k
-quasi planar graphs [2], RAC
graphs [8] and fan-crossing free graphs [6] are closely related to the class of graphs that
we study.
A graph is
k
-planar
, if it can be embedded in the plane with at most
k
crossingsper
edge. Obviously, 1-planar graphs are also fan-planar. A 1-planar graph with
n
vertices
has at most 4
n
−
8 edges and this bound is tight [21]. Grigoriev and Bodlaender [14], and
