Drawing Planar Graphs with Reduced Height - Graph Drawing - page 401

If max ∀i>k +1 {

x holds, then G admits a drawing on L x +4
by Lemma 6. We may thus assume that there exists some j>q such that either
G aw j w j− 1

G aw i w i− 1 ,G bw i w i− 1 }≤

>x or G bw j w j− 1 >x . Hence max ∀i>k +1 ,i = j { G aw i w i− 1 ,G bw i w i− 1 }≤

n / 9.
We first show that G abq can be drawn on L x +3 in two ways: One drawing ʓ 1
contains the vertices a,b,q on l 1 ,l x +3 ,l 2 , respectively, and the other drawing ʓ 2
contains a,b,q on l 1 ,l x +3 ,l x +2 , respectively. We then extend these drawings to
obtain the required drawing of G . Consider the following scenarios depending
on whether G 1 ≤

x or not.

-If G 1 ≤ x . Here we draw the subgraph G induced

by the vertices a,b,p,q such that they lie on l 1 ,l x +3 ,l x +2 ,l 2 , respectively. Since
G 3 ≤

x ,then G 3 ≤ G 2 ≤ G 1 ≤

x , by Lemma 5, G 1 ,G 2 and G 3 can be drawn inside their
corresponding triangles, which corresponds to ʓ 1 . Similarly, we can find another
drawing ʓ 2 of G abq ,wherethevertices a,b,p,q lieon l 1 ,l x +3 ,l 2 ,l x +2 ,respectively.
-If G 1 >x ,then G 3 ≤

G 2 ≤ G 1 ≤

n / 9. We use Chrobak and Nakano's algorithm [6]
and the Stretch condition to draw G 1 on L x +3 layers such that a, b lie on
l 1 ,l x +3 , respectively, and p lies either on l 2 or l n / 3+2 .If l ( p )= l 2 (i.e., ʓ 2 ),
then we place q on l x +2 .Otherwise, l ( p )= l n / 3+2 (i.e., ʓ 1 ), and we place q on
l 2 .Since G 3 ≤

G 2 ≤

n / 9, for each of these two placements we can draw G 2
and G 3 using Lemma 5 inside their corresponding triangles.

G 2 ≤

We now show how to extend the drawing of G abq to compute the drawing of G .
Consider two scenarios depending on whether G aw j w j− 1 >x or G bw j w j− 1 >x .
- Assume that G aw j w j− 1 >x . Shift b to l x +4 , and draw the path w k +1 ,...,w j− 1
in a zigzag fashion, placing the vertices on l 2 and l x +3 alternatively, such that
l ( w k +1 ) = l ( w k +2 ), and each vertex is visible to both a and b .Choose ʓ 1 or ʓ 2

such that the edge ( a, w j− 1 ) spans at least x + 3 lines. We now draw G aw j w j− 1
using Chrobak and Nakano's algorithm [6]. Since x<G aw j w j− 1 ≤ n / 2, we

can draw G aw j w j− 1 on at most n / 3 parallel lines. By the Stretch and Reshape
conditions, we merge this drawing with the current drawing such that w j lies on
either l x +3 or l n / 9+2 .Since G bw j w j− 1 ≤ n / 9, we can draw G bw j w j− 1 inside its
corresponding triangle using Lemma 5. Since max ∀i>j {

G aw i w i− 1 ,G bw i w i− 1 }≤
n / 9, it is straightforward to extend the current drawing to a drawing of G on
x + 4 parallel lines by continuing the path w j ,...,w t in the zigzag fashion.
- Assume that G bw j w j− 1 >x . The drawing in this case is similar to the case when
G aw j w j− 1 >x .Theonlydifferenceisthatwhiledrawingthepath w k +1 ,...,w j− 1 ,
we choose ʓ 1 or ʓ 2 such that the edge ( b,w j− 1 ) spans at least x + 3 lines.

Case 2 ( G 4 ≤ x ). Observe that G 2 ≤ G 1 ≤ n / 2. Since G 3 ≤ G 2 ≤ G 1 and

G 3 + G 2 + G 1 = n +5,wehave G 3 ≤ ( n +2) / 3. Hence G admits a drawing on

L x +4 by Lemma 6.
The following theorem summarizes the result of this section.
Theorem 2. Every n-vertex planar 3 -tree admits a straight-line drawing with
height 4( n +3) / 9+4=4 n/ 9+ O (1) .