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
ID Code:744

Repository Staff Only: item control page

References

H. de Fraysseix and P. Ossona de Mendez. PIGALE: Public Implementation of a Graph Algorithm Library and Editor. Free Software (GPL licence), 2002. http://pigale.sourceforge.net.

H. de Fraysseix and P. Ossona de Mendez. PIGALE. In R. Tamassia, editor, Handbook of Graph Drawing and Visualization, chapter 26. CRC Press, 2006. in preparation.

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.

J.E. Hopcroft and R.E. Tarjan. Efficient algorithms for graph manipulation. Communications of the ACM, (16):372–378, 1973.

J.E Hopcroft and R.E. Tarjan. Efficient planarity testing. J. Assoc. Comput. Math., 21:549–568, 1974.

H. de Fraysseix and P. Rosenstiehl. A characterization of planar graphs by Trémaux orders. Combinatorica, 5(2):127–135, 1985.

H. de Fraysseix and P. Rosenstiehl. Système de référence de Trémaux d’une représentation plane d’un graphe planaire. Annals of Discrete Mathematics, 17:293–302, 1983.

H. de Fraysseix and P. Rosenstiehl. A depth-first search characterization of planarity. Annals of Discrete Mathematics, 13:75–80, 1982.

E. Lucas. Récréations Mathématiques. Paris, 1882.

R.E. Tarjan. Depth-first-search and linear graph algorithm. SIAM J. Comp., 2:146–160, 1972.

S. Even. Graph Algorithms. Computer Science Press, Rockville, MD, 1979.