Lempel, Even, and Cederbaum Planarity Method
Resumo
We present a simple pedagogical graph theoretical description of Lempel, Even, and Cederbaum (LEC) planarity method based on concepts due to Thomas. A linear-time implementation of LEC method using the PC-tree data structure of Shih and Hsu is provided and described in details. We report on an experimental study involving this implementation and other available linear-time implementations of planarity algorithms.
Referências
L. Auslander and S.V. Parter. On imbedding graphs in the plane. J. of Mathematics and Mechanics, 10:517–523, 1961.
K.S. Booth and G.S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. of Comp. and Syst. Sciences, 13:335–379, 1976.
J. Boyer, C. G. Fernandes, W. L. Hsu, A. Noma, and J. C. Pina. Correcting and implementing the PC-tree planarity algorithm. Submetido, 2003.
J. Boyer, C. G. Fernandes, A. Noma, and J. C. Pina. Lempel, Even, and Cederbaum planarity method. In Proc. of the III Workshop on Efficient and Experimental Algorithms, 2004.
J.M. Boyer and W. Myrvold. On the cutting edge: Simplified O(n) planarity by edge addition. Preprint, 29pp.
S. Even and R.E. Tarjan. Computing an st-numbering. Theor. Comp. Science, 2:339–344, 1976.
A.J. Goldstein. An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. In Graph and Combinatorics Conf., 1963.
J. Hopcroft and R. Tarjan. Efficient planarity testing. J. of the ACM, 21(4):549–568, 1974.
A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In P. Rosenstiehl, editor, Theory of Graphs, pages 215–232, New York, 1967. Gordon and Breach.
A. Noma. Análise experimental de algoritmos de planaridade (in Portuguese). Master’s thesis, Universidade de São Paulo, 2003.
W.K. Shih and W.L. Hsu. A simple test for planar graphs. In Proc. of the International Workshop on Discrete Math. and Algorithms, pages 110–122. University of Hong Kong, 1993.
R. Thomas. Planarity in linear time. [link], 1997.
K.S. Booth and G.S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. of Comp. and Syst. Sciences, 13:335–379, 1976.
J. Boyer, C. G. Fernandes, W. L. Hsu, A. Noma, and J. C. Pina. Correcting and implementing the PC-tree planarity algorithm. Submetido, 2003.
J. Boyer, C. G. Fernandes, A. Noma, and J. C. Pina. Lempel, Even, and Cederbaum planarity method. In Proc. of the III Workshop on Efficient and Experimental Algorithms, 2004.
J.M. Boyer and W. Myrvold. On the cutting edge: Simplified O(n) planarity by edge addition. Preprint, 29pp.
S. Even and R.E. Tarjan. Computing an st-numbering. Theor. Comp. Science, 2:339–344, 1976.
A.J. Goldstein. An efficient and constructive algorithm for testing whether a graph can be embedded in a plane. In Graph and Combinatorics Conf., 1963.
J. Hopcroft and R. Tarjan. Efficient planarity testing. J. of the ACM, 21(4):549–568, 1974.
A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In P. Rosenstiehl, editor, Theory of Graphs, pages 215–232, New York, 1967. Gordon and Breach.
A. Noma. Análise experimental de algoritmos de planaridade (in Portuguese). Master’s thesis, Universidade de São Paulo, 2003.
W.K. Shih and W.L. Hsu. A simple test for planar graphs. In Proc. of the International Workshop on Discrete Math. and Algorithms, pages 110–122. University of Hong Kong, 1993.
R. Thomas. Planarity in linear time. [link], 1997.
Publicado
31/07/2004
Como Citar
NOMA, Alexandre; FERNANDES, Cristina G..
Lempel, Even, and Cederbaum Planarity Method. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 17. , 2004, Salvador/BA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2004
.
p. 99-103.
ISSN 2763-8820.
