16 CHAPTER 1. PLANARITY TESTING AND EMBEDDING
• all return edges of e
2
ending strictly higher than lowpt(e
1
) belong to t he other
class.
Intuitively, the partition of the back edges into classes L and R corr e sponds to orienting
the fundamental cycles in such a way that those closed by back edges in L are counterclock-
wise while those closed by back edges in R ar e clockwise.
Theorem 1.2 A graph is planar if and only if it admits an LR partition.
Necessity of the condition of Theorem 1.2 is straightforward: given a DFS tree and a
planar embedding of the graph it suffices to assign each back edge to the classes L or
R, depending on whether the fundamental cycle it closes is counterclockwise or clockwise,
respectively. Sufficiency is shown by constructing ...