1.7. VERTEX ADDITION ALGORITHMS 21
the whole graph is obtained. Finally, the following lemma shows that if the process stops,
the graph is not planar.
LEMMA 1.7 Let G be a graph and let ψ be any proper numbering of G. Denote by G
i
,
with i = 1, . . . , n the su bgr aph of G induced by vertices in V
i
= {v | ψ(v) ≤ i} and by
B
1
i
, B
2
i
, . . . , B
b
i
i
the b
i
blocks of G
i
. For a given k, 1 ≤ k ≤ n −1, let Γ(B
j
k
), 1 ≤ j ≤ b
k
, be
arbitrary embeddings of B
j
k
with the outer vertices of G
k
on their outer faces. If the blocks
of G
k+1
cannot be embedded such that the outer vertices of G
k+1
are on the outer face and
Γ(B
j
k
), 1 ≤ j ≤ b
k
, are preserved up to a flip, then G is not planar.
Proof: Suppose for a contradiction that G is planar and that there is no planar embedding ...