Drawing Outer 1-planar Graphs with Few Slopes - Graph Drawing - page 178

˄ μ

˄ μ ˄ μ

ʓ ʷ 2
ʱ − ʵ

ʓ ˈ 1 ʓ ˈ k

ʓ ʷ 1

s μ t μ

ʓ ʷ 1 ʓ ʷ k

s μ t μ

ʱ ʱ

s μ t μ

ʱ − ʵ

(a) (b) (c)

˄ μ ˄ μ

ʓ ʷ 2

ʓ ʷ

ʓ ʷ 1

ʓ ʷ 1 ʓ ʷ 3

ʓ ˈ

ʓ ʷ 5 ʓ ʷ 4

s μ t μ s μ t μ 2 ʱ

(d) (e)

Fig. 2. The drawing of the pertinent graph of: (a) an S -node; (b) a P -node with two children such
that one is a Q -node and the other one is an S -node; (c) a P -node with two children such that none
of them is a Q -node; (d) an S ∗ -node; (e) an R -node. Edges drawn with red slopes are dashed.

the only two children of ʽ , then we also replace ʽ with ˕ . The pertinent graph of ˕ is

G ˕ = G μ ∪ is ( s μ , t ʷ ),if

G ʷ , while the reference edgeof ˕ μ is AOS with respect to s μ ,

or ( s ʷ , t μ ),if is OS . By means of this

transformation we can consider only P -nodes that are OS . Similarly we can handle just
S -nodes whose children are OS . In what follows we distinguish between S -, P -, S ∗ -, and
R -nodes different from

μ is AOS with respect to t μ . It is easy to see that ˕

ʾ .

Lemma 1. Let μ be an S-node differentfrom ʾ .ThenG μ admits a straight-linedrawing

ʓ μ that respects Invariants I1. , I2. and I3 .

1 , 2 ,..., Proof sketch: The drawings of the pertinent graphs of the children ʷ ʷ ʷ k of μ

are attached to each other as shown in Figure 2(a). Clearly all invariants hold.

Lemma 2. Let μ be aP-node differentfrom ʾ .ThenG μ admits a straight-linedrawing

ʓ μ that respects Invariants I1. , I2. and I3 .

Proof sketch: Recall that, thanks to the definition of S ∗ -nodes, here we need to only
handle only P -nodes that are OS .ByProperty 3, one of the following cases applies: ( i )
μ has two

children and none of them is a Q -node. Then both are OSS -nodes, one of them has a
tail at s μ , and the other one has a tail at t μ . Also, the two edges associated with these
two tails cross each other in G . ( iii )

has two children one of which is a Q -node and the other one is OS . ( ii ) μ

has three children and one of them is a Q -node.
For the remaining two children case ( ii ) applies.
Case ( i ) can be easily handled as shown in Figure 2(b). Consider case ( ii ) and let

μ

ʷ 1

be the child of μ that is an S -node with a tail at t μ ,and ʷ 2 be the child of μ that is an S -

node with a tail at s μ . Refer to Figure 2(c). Recall that s ʷ 1 = s ʷ 2 = s μ and t ʷ 1 = t ʷ 2 = t μ .

We modify the drawing ʓ ʷ 1 as follows. We first rotate ʓ ʷ 1 so that the segment s ʷ 1 t ʷ 1 uses

ʷ 1 using the red slope r 2ʔ the blue slope b 2 . Then we redraw the tail of = b 2ʔ + ʵ and

so that s ʷ 1 and t ʷ 1 are horizontally aligned. Similarly, we modify the drawing ʓ ʷ 2 .We

rotate ʓ ʷ 2 so that the segment s ʷ 2 t ʷ 2 uses the blue slope b 2ʔ and redraw the tail of ʷ 2