基于Hopcroft-Tarjan判定算法的平面图嵌入算法  

An Embedding Algorithm for Planar Graph Based on the Hopcroft-Tarjan Testing Algorithm

作　　者：魏品帅[1] 黄竞伟[1] 

机构地区：[1]武汉大学计算机学院,武汉430072

出　　处：《计算机工程》2003年第15期63-65,共3页Computer Engineering

基　　金：国家自然科学基金项目(60173045)

摘　　要：给出了一个基于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.

关 键 词：图 平面图 算法 嵌入算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP301.6[自动化与计算机技术—计算机科学与技术]