
322 CHAPTER 10. RECTANGULAR DRAWING ALGORITHMS
(iii) d(v) = 4.
Thus n
1
= 2 for the example in Fig. 10.5. One may assume as a trivial necessary condition
that n
1
≤ 4; otherwise, G has no rectangular drawing. Exactly 4 − n
1
of the n
x
angles of
F labeled with x must be labeled with 1 by a regular labeling. Add a complete bipartite
graph K
(4−n
1
),n
x
in F , and join each of the n
x
vertices in the second partite set with one of
the n
x
vertices on F whose angles are labeled with x. Repeat the operation above for each
inner face F of G. The resulting graph is a decision graph G
d
of G. The decision graph
G
d
of the plane graph G in Fig. 10.4(a) is drawn by solid lines ...