Lempel, Even, and Cederbaum Planarity Method

1. Auslander, L., Parter, S.V.: On imbedding graphs in the plane. Journal of Mathematics and Mechanics 10, 517–523 (1961)

   MATH  MathSciNet  Google Scholar 

2. Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ–tree algorithms. Journal of Computer and Systems Sciences 13, 335–379 (1976)

   Article  MATH  MathSciNet  Google Scholar 

3. Boyer, J.M., Cortese, P.F., Patrignani, M., Di Battista, G.: Stop minding your P’s and Q’s: Implementing a fast and simple DFS-based planarity testing and embedding algorithm. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 25–36. Springer, Heidelberg (2004)

   Chapter  Google Scholar 

4. Boyer, J.M., Myrvold, W.: On the cutting edge: Simplified O(n) planarity by edge addition, p. 29 (preprint)

   Google Scholar 

5. Boyer, J.M., Myrvold, W.: Stop minding your P’s and Q’s: A simplified O(n) planar embedding algorithm. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 140–146 (1999)

   Google Scholar 

6. Chiba, N., Nishizeki, T., Abe, A., Ozawa, T.: A linear algorithm for embedding planar graphs using PQ–trees. Journal of Computer and Systems Sciences 30, 54–76 (1985)

   Article  MATH  MathSciNet  Google Scholar 

7. Deo, N.: Note on Hopcroft and Tarjan planarity algorithm. Journal of the Association for Computing Machinery 23, 74–75 (1976)

   MATH  MathSciNet  Google Scholar 

8. Even, S., Tarjan, R.E.: Computing an st-numbering. Theoretical Computer Science 2, 339–344 (1976)

   Article  MATH  MathSciNet  Google Scholar 

9. Goldstein, A.J.: An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. In Graph and Combinatorics Conf. Contract No. NONR 1858-(21), Office of Naval Research Logistics Proj., Dep. of Math., Princeton U., p. 2 (1963)

   Google Scholar 

10. Hopcroft, J., Tarjan, R.: Efficient planarity testing. Journal of the Association for Computing Machinery 21(4), 549–568 (1974)

    MATH  MathSciNet  Google Scholar 

11. Hsu, W.L.: An efficient implementation of the PC-tree algorithm of Shih & Hsu’s planarity test. Technical report, Inst. of Information Science, Academia Sinica (2003)

    Google Scholar 

12. Jünger, M., Leipert, S., Mutzel, P.: Pitfalls of using PQ-trees in automatic graph drawing. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 193–204. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

13. Lempel, A., Even, S., Cederbaum, I.: An algorithm for planarity testing of graphs. In: Rosenstiehl, P. (ed.) Theory of Graphs, pp. 215–232. Gordon and Breach, New York (1967)

    Google Scholar 

14. Mehlhorn, K., Näher, S.: The LEDA Platform of Combinatorial and Geometric Computing. Cambridge Press, Cambridge (1997)

    Google Scholar 

15. Noma, A.: Análise experimental de algoritmos de planaridade. Master’s thesis, Universidade de São Paulo (2003) (in Portuguese), http://www.ime.usp.br/dcc/posgrad/teses/noma/dissertation.ps.gz

16. Reingold, E.M., Nievergelt, J., Deo, N.: Combinatorial Algorithms: Theory and Practice. Prentice-Hall, Inc., Englewood Cliffs (1977)

    Google Scholar 

17. Shih, W.K., Hsu, W.L.: A simple test for planar graphs. In: Proceedings of the International Workshop on Discrete Math. and Algorithms, pp. 110–122. University of Hong Kong (1993)

    Google Scholar 

18. Shih, W.K., Hsu, W.L.: A new planarity test. Theoretical Computer Science 223, 179–191 (1999)

    Article  MATH  MathSciNet  Google Scholar 

19. Thomas, R.: Planarity in linear time (1997), http://www.math.gatech.edu/~thomas/

20. Williamson, S.G.: Embedding graphs in the plane – algorithmic aspects. Ann. Disc. Math. 6, 349–384 (1980)

    Article  MATH  Google Scholar 

21. Williamson, S.G.: Combinatorics for Computer Science. Computer Science Press, Maryland (1985)

    Google Scholar 

22. Williamson, S.G.: Personal Communication (August 2001)

    Google Scholar 

Download references