
604 CHAPTER 19. PIGALE
7 6
5
4
2 8
1 3
1
−1
11
−11
4
−4
−14
14
−6
6
5
−3
3
−10
10
−2
2
−13
−9
9
−12
12
−7
7
−8
8
−5
13
Figure 19.3 DFS numbering of a combinatorial map.
Figure 19.4 A Kuratowski subdivision in a nonplanar graph.
This algorithm relies on the concept of DFS cotree-critical graphs, which is a by-product
of our planarity testing algorithms. Roughly speaking, a DFS cotree-critical graph is a
simple graph of minimum degree 3 having a DFS tree, such that any nontree (i.e., cotree)
edge is critical, in the sense that its deletion would lead to a planar graph. A first study of
DFS cotree-critical ...