
26 CHAPTER 1. PLANARITY TESTING AND EMBEDDING
(a) (b)
Figure 1.14 (a) Relevant nodes of T
i−1
have one terminal. (b) Relevant nodes of T
i−1
have two terminals.
(a) (b)
Figure 1.15 (a) The example of Figure 1.14(a) after contraction. The double border
identifies C-nodes. (b) The example of Figure 1.14(b) after contraction.
on one side of T
i−1
, and the embedded part can be replaced with a C-node, as shown in
Figure 1.15(a).
The case when T
i−1
has exactly one terminal and some relevant node is a C-node, is
analogous, with the difference that the constr aints enforced by C-nodes (whose adjacency
list can only be flipped) have to be taken into ...