Depth-First Search and Planarity
Hubert de Fraysseix, Patrice Ossona de Mendez, Pierre Rosenstiehl · arXiv (Cornell University) · 2006
We present a simplified version of the DFS-based Left-Right planarity testing and embedding algorithm implemented in Pigale (1, 2), which has been considered as the fastest implemented one (3). We give here a full jus- tification of the algorithm, based on a topological properties of Tremaux trees.