Information Technology Reference
In-Depth Information
independently Kohrzik and Mohar [19] proved that the problem of determining whether
a graph is 1-planar is NP-hard. On the positive side, Eades et al. [9] presented a linear
time algorithm for testing
maximal1-planarity
of graphs with a given rotation system.
Testing
outer-
1
-planarity
of a graph can be solved in linear time, as shown indepen-
dently by Auer et al. [4] and Hong et al. [16]. In addition, every outer-1-planar graph
admits an outer-1-planar straight-line drawing [11]. Note that an outer-1-planar graph is
always planar [4], while this is not trueingeneral for outer-fan-planar graphs. Indeed,
the complete graph
K
5
is outer-fan-planar, but not planar. Recently, it was shown that
testing
full outer-2-planarity
(i.e., outer-2-planar embedding with no crossing on the
outer face) of graphs can be solved in linear time [17].
Adrawngraph is
k
-quasi planar
if it has no
k
mutually crossing edges. It is conjec-
tured that the number of edges of a
k
-quasi planar graph is linear in the number of its
vertices. Pach et al. [20] and Ackerman [1] affirmatively answered this conjecture for
3-and4-quasi planar graphs. Fox and Pach [12] showed that a
k
-quasi-planar
n
-vertex
graph has at most
O
(
n
log
1+
o
(1)
n
) edges. Fan planar graphs are 3-quasi planar [18].
A different forbidden crossing pattern arises in RAC drawingswheretwoedges are
allowed to cross, if the crossingsedges form right angles. Graphs that admit such draw-
ings (with straight-line edges) are called
RAC graphs
. Didimo et al. [8] showed that a
RAC graph with
n
vertices has no more than 4
n
10 edges; a tight bound. RAC graphs
are quasi planar [8], while
maximally dense
(i.e., exactly 4
n
−
10 edges) RAC graphs
are 1-planar [10]. Testing whether a graph is RAC is NP-hard [3], while testing outer-
RAC graphs with a given vertex ordering and a rotation system can be solved in linear
time [7].
−
Preliminaries.
Unless otherwise specified, we consider finite, undirected, simple
graphs. We also assume basic familiarity with SPQR-trees [15] (a short introduction
is given in [5]). The
rotation system
of a drawing is the counterclockwise order of the
incident edges around each vertex. The
embedding
of a drawn graph consists of its ro-
tation system and for each edgethesequence of edges crossing it. For a graph
G
and a
vertex
v
∈
V
[
G
], we denote by
G
−{
v
}
the graph that results from
G
by removing
v
.
Lemma 1.
Abiconnected graph
G
is outer-fan-planarifandonly if it admits a straight-
lineouter-fan-planardrawing inwhich the vertices of
G
are restricted onacircle
C
.
Sketch of Proof.
Let
G
be an outer-fan-planar graph and let
ʓ
be an outer-fan-planar
drawing of
G
. We will only show that
G
has a straight-line outer-fan-planar drawing
whose vertices lie on a circle
(the other direction is trivial). The order of the vertices
along the outer face of
ʓ
completely determines whether two edges cross, as in a simple
drawing no two incident edges can cross and any two edges can cross at most once.
Now, assume that two edges cross another edgein
ʓ
. Then, both edges have to be
incident to the same vertex; hence, cannot cross each other. So, the order of the crossings
on an edge is also determined by the order of the vertices on the outer face. Therefore,
we can construct a drawing
ʓ
C
C
preserving
their order in the outer face of
ʓ
and draw the edges as straight-line segments.
by placing the vertices of
G
on a circle
C
