
8.3. RESULTS IN THE GENERAL SCENARIO 257
graph. I ns t ead, the sequence of vertices is such that, if du mmy edges are inserted between
non-adjacent vertices that are consecutive in the sequence, then the resulting drawing is
still a k-spine, 1-bend drawing. The following lemma holds.
LEMMA 8.2 If G is a maximal planar graph that is k-spine, 1-ben d drawable for k ≥ 2,
then there exists a simple cycle C in G such that G \ C is (k − 1)-spine, 1-bend drawable.
(a)
(b)
Figure 8.7 (a) A planar 2-spine, 1-bend drawing of a planar graph G. (b) A cutting cycle
of G. Figure taken from [DD LS 06].
We can use now the neces s ary condition expressed by Lemma 8.2 ...