A linear algorithm for embedding planar graphs using PQ-trees
作者： Norishige Chiba , Takao Nishizeki , Shigenobu Abe , Takao Ozawa
DOI: 10.1016/0022-0000(85)90004-2
关键词: Planarity testing 、 Tarjan's strongly connected components algorithm 、 Graph embedding 、 Mathematics 、 Planar graph 、 Linkless embedding 、 Planar straight-line graph 、 Topological graph theory 、 Book embedding 、 Combinatorics 、 Discrete mathematics 、 Theoretical computer science 、 Computer Networks and Communications 、 Computational Theory and Mathematics 、 Applied mathematics
摘要: Abstract This paper presents a simple linear algorithm for embedding (or drawing) planar graph in the plane. The is based on “vertex-addition” of Lempel, Even, and Cederbaum (“Theory Graphs,” Intl. Sympos. Rome, July 1966, pp. 215–232, Gordon & Breach, New York, 1967) planarity testing, modification Booth Lueker's (J. Comput. System Sci. 13 (1976), 335–379) implementation testing using PQ-tree. Compared with known Hopcroft Tarjan Assoc. Mach. 21, No. 4 (1974), 549–568), this conceptually easy to understand or implement. Moreover can find all embeddings graph.
acm.org
elsevier.com
sci-hub.se 参考文章(6)
John Hopcroft, Robert Tarjan, Efficient Planarity Testing Journal of the ACM. ,vol. 21, pp. 549- 568 ,(1974) , 10.1145/321850.321852
J. E. Hopcroft, R. E. Tarjan, Dividing a Graph into Triconnected Components SIAM Journal on Computing. ,vol. 2, pp. 135- 158 ,(1973) , 10.1137/0202012
Kellogg S. Booth, George S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms Journal of Computer and System Sciences. ,vol. 13, pp. 335- 379 ,(1976) , 10.1016/S0022-0000(76)80045-1
Shimon Even, Robert Endre Tarjan, Computing an st-numbering Theoretical Computer Science. ,vol. 2, pp. 339- 344 ,(1976) , 10.1016/0304-3975(76)90086-4
Shimon Even, Graph Algorithms ,(1979)
Frank Harary, Graph theory ,(1969)