Information Technology Reference
In-Depth Information
s
μ
s
μ
t
μ
t
μ
s
μ
s
μ
t
μ
t
μ
s
ʽ
t
ʽ
(a)
(b)
(c)
(d)
Fig. 1.
Illustration of Properties 2- 4. The pertinent graph of: (a) an
R
-node
μ
;(b)a
P
-node
μ
(case (
ii
) of Property 3);. (c) a
P
-node
μ
that is
AOS
with respect to
s
μ
;(d)An
S
-node
ʽ
with a
child μ
that is
AOS
with respect to
s
μ
.Dashededges cross in the embedding of the graph.
1-planar drawing
ʓ
of a graph
G
each crossed edge is divided into two
edgefragments
.
Also in this case,
partitions the plane into topologically connected regions, which
we call faces. A 1
-planarembedding
of a 1-planar graph is an equivalence class of
1-planar drawings that define the same set of faces. An
outer 1-planardrawing
is a 1-
planar drawing with all vertices on the outer face. An
outer 1-plane graphG
is a graph
with a given outer 1-planar embedding.
The slope
s
of a line
is the angle that an horizontal line needs to be rotated counter-
clockwise in order to make it overlap with
. The slope of a segment representing an
edgeinastraight-line drawing is the slope of the supporting line containing the segment.
Ourdrawing techniques use
SPQR
-trees, whose definition can be found in [6].
Properties of Outer 1-planar Graphs.
The structural properties of outer 1-planar
graphs have been studied in [2,11]. In this paragraph we derive properties that hold
in the fixed outer 1-planar embedding setting and that easily follow from the results
in [11]. In Section 4 we will use the same properties explaining how to adapt them to
the planar embedding setting. The following property can be foundasLemma1in[11].
ʓ
Property 1.
Let
G
be an outer 1-plane graph. If
G
is triconnected, then it is isomorphic
to
K
4
and it has exactly one crossing.
In what follows we consider a biconnected outer 1-plane graph
G
and its
SPQR
-tree
T
.Let
μ
be a node of
T
,the
pertinent graphG
μ
of
μ
is the subgraph of
G
whose
SPQR
-
tree (with respect to the reference edge
e
of
. Notice
that the edge
e
is not part of
G
μ
.Fromnowonweassume
G
μ
to be an outer 1-plane
graph using the embedding induced from
G
.Wegive the following definition [11].
μ
)isthesubtree of
T
rooted at
μ
Definition 1.
A node
of T is onesidedwith respect to its poles s
μ
andt
μ
,orsimply
OS,iftheedge
(
s
μ
,
t
μ
)
is on theouter face of G
μ
.
μ
Furthermore, we consider
T
to be rooted at a
Q
-node
ˁ
whose (only) child is denoted
by
to be associated with an edge that is not crossed and
that belongs to the boundary of the outer face of
G
. It can be shown that such an edge
always exists. This choice implies that
ʾ
. In particular, we choose
ˁ
is
OS
by definition. The next property derives
from Lemma 5 in [11] and defines the structure of the skeleton of
R
-nodes, see also
Figure 1(a).
ʾ
Property 2.
Let
μ
be an
R
-node of
T
. Then: (
i
) The skeleton
˃
(
μ
) is isomorphic to
K
4
and it has one crossing; (
ii
) The children of
μ
are all
OS
; (
iii
) Two children of
μ
are
Q
-nodes whose associated edges cross each other in
G
μ
.
