
342 CHAPTER 10. RECTANGULAR DRAWING ALGORITHMS
There are infinitely many cycles with four designated vertices for which the sum of the
width and the height of any box-rectangular drawing of the cycles is m − 2.
The rest of this section deals with a general case where no vertices are designated as corner
boxes in advance. Then our problem is how to examine whether G has some set of outer
vertices such that there is a box-rectangular drawing of G having them as the corner boxes,
and how to find them if there are. We first present a necessary and sufficient condition
for a plane graph G with ∆ ≤ 3 to have a box-rectangular drawing D as in Theorem 10.7
[RNN00], ...