Trémaux trees and planarity

De Fraysseix, Hubert and Ossona de Mendez, Patrice and Rosenstiehl, Pierre (2006) Trémaux trees and planarity. [Journal (Paginated)]

Full text not available from this repository.

Abstract

We present a simplified version of the DFS-based Left-Right planarity testing and embedding algorithm implemented in Pigale which has been considered as the fastest implemented one [J.M. Boyer, P.F. Cortese, M. Patrignani, and G. Di Battista. Stop minding your P's and Q's: implementing fast and simple DFS-based planarity and embedding algorithm. In Graph Drawing, volume 2912 of Lecture Notes in Computer Science, pages 25-36. Springer, 2004.]. We give here a simple full justification of the algorithm, based on a preliminary extended study of topological properties of DFS trees.

Item Type:	Journal (Paginated)
Additional Information:	10.1142/S0129054106004248
Classifications:	M Methods > M.900 Tree M Methods > M.600 Planar G Algorithms and Complexity > G.490 Embeddings G Algorithms and Complexity > G.770 Planarity Testing
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/744

Actions (login required)

View Item