Logo

Login

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)
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
Deposited By:Ossona de Mendez, Patrice
Deposited On:05 Oct 2006
Last Modified:18 Sep 2008 13:09

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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.