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

s ʷ 6 = s μ belongs to the line with slope g 2 passing through s ʷ 5 . We now rotate ʓ ʷ 1 so

that the segment s ʷ 1 t ʷ 1 uses the green slope g 2 and attach it to ʓ ʷ 5 and ʓ ʷ 6 . Finally, the

edge corresponding to ʷ

4 is drawn as the segment s μ s ʷ 3 .Invariant Ia. holds because the

drawings ʓ ʷ 1 , ʓ ʷ 2 , ʓ ʷ 3 , ʓ ʷ 4 , ʓ ʷ 5 ,and ʓ ʷ 6 do not intersect each other except at common

endpoints. Aboutthis,let ˄ be the triangle defined by the three vertices s μ , s ʷ 3 ,and

s ʷ 5 ; it is easy to see that ʓ ʷ 2 is completely contained inside ˄ except for the segment

2 +

s ʷ 3 s ʷ 5 that ʓ ʷ 2 shares with ˄ . Namely the angle inside ˄ at s ʷ 3 is ʸ , while the angle

is at least 4 < 4 ). Since

inside ˄ at s ʷ 5 (because the angle inside ˄ at s μ is ʸ and 2 ʸ

ʲ ʷ 2 < 4 ʳ ʷ 2 < 4 , the triangle except for the vertical side

shared by the two triangles. Concerning Invariant Ib. , we observe that

and ˄ ʷ 2 is completely inside ˄

ʓ ʷ 1 , ʓ ʷ 2 , ʓ ʷ 3 ,

ʓ ʷ 4 ,and ʓ ʷ 5 are rotated by an angle that is a multiple of ʸ and therefore Ib. holds by

construction for each of them. We now show that the slope ˆ of the edge corresponding

to ʷ 4 is in fact either a green slope or a yellow one (refer to Figure 3(f)). Let ʴ x 1 be the

horizontal distance between s ʷ 3 and t μ and let ʴ x 2 be the horizontal distance between s μ

and s ʷ 3 .Bysimpletrigonometry we have ʴ x 1 tan( g 4ʔ )= ʴ x 2 tan( ˆ ) and ʴ x 1 tan( g j )=

ʴ x 2 tan( g 3 ),where g j is the slope of the segment representing the edge corresponding

to ʷ 5 (and therefore j = 4 ʔ − ʔ ( t ʷ 3 )). From the two previousequations we obtain

tan(ˆ)= tan( g 4ʔ )tan( g 3 )
tan( g j )

. Notice that 1 ≤ ʔ( t ʷ 3 ) ≤ ʔ and therefore 3 ʔ ≤ j ≤ 4 ʔ − 1. If

j = 4 ʔ − 1, then tan( g 3 )= − tan( g j ) and tan( ˆ )= − tan( g 4ʔ )=tan( g 2 ), hence ˆ = g 2 ,

= arctan tan( g 4ʔ )tan( g 3 )
tan( g j )

= and therefore

i.e., ˆ is a green slope. Otherwise ˆ ˆ is the

yellow slope y 1 , j (recall that g 1 = 0). Concerning Invariant Ic. ,wehavethat ʔ ( s μ )=

ʸ ≤

−

ʔ ( s ʷ 1 )+2and ʔ ( t μ )= ʔ ( t ʷ 3 )+2. Moreover, ʲ μ = ʲ ʷ 1 + 2 ( ʔ ( s ʷ 1 ) 1) ʸ + 2 ʸ =

−

ʸ ≤

− −

( ʔ ( s μ ) 1) ʸ . Finally, ʳ μ = ʳ ʷ 3 + 2 ( ʔ ( t ʷ 3 ) 1) ʸ + 2 ʸ =( ʔ ( t μ ) 1) ʸ .

Lemma 11. Let ˁ be the root of T andlet ʾ be its uniquechild. GraphG = G ˁ ∪ G ʾ

admits a straight-linedrawing ʓ that respects Invariants Ia. , Ib. and Ic .

ByLemmas7,8,9,10,and11,wecanprovethefollowing lemma.
Lemma 12. Let G be a biconnected outer 1 -plane graphwithnvertices and withmax-
imum degree

2

ʔ . Gadmits a planarstraight-linedrawing that uses at most 4 ʔ − 4 ʔ

slopes. Also, this drawing can be computed in O ( n ) time.

The result above can be extended to simply connected outer 1-planar graph with the
same technique described in Section 3. We obtain the following theorem.

Theorem 2. Let G be an outer 1 -plane graphwithnvertices and withmaximum degree
ʔ

2 + 12

. Gadmits a planarstraight-linedrawing that uses at most 4 ʔ ʔ + 8 slopes.

Also, this drawing can be computed in O ( n ) time.

5 Open Problems

An interesting open problem motivated by ourresult of Section 3 is whether the 1 -
planar slope number of 1-planar straight-line drawable graphs (not all 1-planar graphs
admit a 1-planar straight-line drawing [12]), is bounded in or not. A second problem

is whether the quadratic upper bound of Section 4 is tight or not. Finally, it could be
interesting to further explore trade-offs between slopes and crossings, e.g., can we draw
planar partial 3-trees with o (

ʔ

5 ) slopes and a constant number of crossings per edge?

ʔ