
10.3. LINEAR ALGORITHMS FOR RECTANGULAR DRAWING 327
(b)
C
(d)
G
G
1
2
G
3
(f)
P
C
(a)
(e)
G
G
1 2
G
3
G
G
3
1
G
2
(c)
P
cc
c
Figure 10.11 (a) G, (b) splitting G along a single path P
cc
, (c) splitting G along two
paths P
cc
and P
c
, (d) rectangular drawings of three subgraphs, (e) deformation, and (f)
rectangular drawing of G. (Figure taken from [NR04].)
(i) P does not contain any vertex in the proper inside of C, and
(ii) the intersection of C and P is a single subpath of P ,
as illustrated in Fig. 10.12. Let v
t
be the starting vertex of the subpath, and let v
h
be the
ending vertex. We then call v
t
the tail vertex of C for P , and v
h
the head vertex. Denote
by Q
c
(C) the path on C turning ...