
332 CHAPTER 10. RECTANGULAR DRAWING ALGORITHMS
P
W
P
N
P
E
P
S
C
S
P
W
P
N
P
E
P
C
P
P
P
P
N
P
W
P
S
P
E
P
W
P
S
P
N
P
E
i
i
i
i
i
+1
+1
P
i
Figure 10.16 Two alternative rectangular embeddings of cycle C
i
. (Figure taken
from [NR04].)
LEMMA 10.4 If G has no bad cycle and has no boundary NS-, SN-, EW- or WE-path,
then G has a partition-pair P
c
and P
cc
.
Using Lemmas 10.1, 10.2, 10.3 and 10.4, one can recursively find a rectangular drawing
of a given plane graph G if G has no bad cycle. Thus the sufficiency of Theorem 10.2 can
be constructively proved.
10.3.2 Drawing Algorithms
In this section, we assume that a given plane graph G has no bad cycle, and present an
algorithm Rectangular-Draw to find a rectangular ...