基于Hopcroft-Tarjan判定算法的平面图嵌入算法
An Embedding Algorithm for Planar Graph Based on the Hopcroft-Tarjan Testing Algorithm
摘要
给出了一个基于Hopcroft-Tarjan平面图判定算法的平面图嵌入算法，并具体实现了该算法。与其它基于Hopcroft-Tarjian平面图判定算法的嵌入算法的实现方法相比，该方法更容易实现，并且判定和嵌入同时完成。
This paper describes an embedding algorithm for planar graphs based on the Hopcroft-Tarjan Planarity Testing algorithm. Comparing to other embedding algorithms, the proposed algorithm is easy to be implemented , planarity testing and embedding are finished at the same time.
出处
《计算机工程》
CAS
CSCD
北大核心
2003年第15期63-65,共3页
Computer Engineering
基金
国家自然科学基金项目(60173045)
关键词
图
平面图
算法
嵌入算法
Graph
Planar graph
Algorithm
Embedding algorithm
参考文献7
-
1Battista G D, Eades P, Tamassia R, et al. Algorithms lbr Drawing Graphs: An Annotated Bibliography. Computational Geometry: Theory and Applications, 1994,4(5):235 -282.
-
2Battista G D, Eades P, Tamassia R, et al. Graph Drawing: Algorithms for the Visualization of Graphs. New Jersey: Prentice-Hall, 1999.
-
3Lempel A, Even S, Cederbaum I. An Algorithm for Planarity Tesling of Graphs. Theory of Graphs, Int. Syrup., 1966:215-232.
-
4Hopcroft J, Tarjian R. Efficient Planarity Testing. J. ACM, 1974,21(4):549-568.
-
5Chiba N, Nishizeki T, Abe S, et al. A Linear Algorithm for Embedding Planar Graphs Using PQ-trees. J. of Computer and System Sciences,30( 1 ):54-76.
-
6Mehlhorn K, Mutzel P. On the Embedding Phase of the Hopcrott and Tarian Planarity Testing Algorithrn. Max-Planck-Institute Fur Informatik, Im Stadtwald,66123 Saarbrucken, Germany ,1995.
-
7Reingold E M, Nievergelt J, Deo N. Combinatorial Algorithms: Theory and Practice. Prentice-Hall, 1977.
-
1吴德林.数字水印的研究与实现[J].中国科技信息,2012(11):122-122.
-
2展馆平面图[J].自动化信息,2007(4):7-7.
-
3展馆平面图[J].自动化信息,2009(4):6-6.
-
4展馆平面图[J].自动化信息,2005(4).
-
5展馆平面图[J].自动化信息,2006(3):7-7.
-
6邓伟萍.数字水印技术及研究进展[J].网络安全技术与应用,2005(12):58-60.
-
7蒋灏东.浅析数字水印算法与健壮性[J].信息与电脑（理论版）,2010(4):165-165.
-
8柳楠,于晓康,柴乔林.利用图像进行信息压缩和隐藏[J].计算机工程与应用,2004,40(28):76-77. 被引量：1
-
9常卫东,刘完芳,童宇.信息隐藏技术综述[J].中国科技信息,2010(3):117-118. 被引量：2
-
10莫则尧,李晓梅.蝶网在混洗交换网中的一种嵌入算法[J].计算机学报,1995,18(7):545-549.
