TRÉMAUX TREES AND PLANARITY
- 1 October 2006
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 17 (05) , 1017-1029
Abstract
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 justification of the algorithm, based on a topological properties of Trémaux trees.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Stop Minding Your P’s and Q’s: Implementing a Fast and Simple DFS-Based Planarity Testing and Embedding AlgorithmLecture Notes in Computer Science, 2004
- A characterization of planar graphs by trémaux ordersCombinatorica, 1985
- Efficient Planarity TestingJournal of the ACM, 1974