
10.4. BOX-RECTANGULAR DRAWING 337
(c) 2c
2
+c
3
≤ 4 for every independent set S of cycles consisting of 2-legged cycles and
3-legged cycles, where c
2
and c
3
are the numbers of 2-legged cycles and 3-legged
cycles in S, respectively.
Figure 10.22 Plane graph. (Figure taken from [NR04].)
For the set S
1
= {C
1
, C
2
} above c
2
= 2, c
3
= 0 and hence 2c
2
+ c
3
= 4, while for
S
2
= {C
2
, C
3
, C
4
} c
2
= 1 and c
3
= 2 and hence 2c
2
+ c
3
= 4.
It is rather easy to prove the necessity of Theorem 10.4.
In order to prove the sufficiency of Theorem 10.4, it suffices to show that if the three
conditions (a)–(c) in Theorem 10.4 hold then one can choose four outer vertices of degree ...