Planarity Testing and Embedding
Planarity Testing and Embedding
复制标题
平面度测试和嵌入
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
M. Patrignani
中科院分区：
文献类型：
--
作者：
M. Patrignani
罗马三大学1.1平面图的性质和表征. . . . .2基本定义•性质•特征1.2平面性问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6约束平面性•删除和分区问题•向上平面性•外平面性•同时平面性•聚类平面性1.3平面性算法的历史. . . . . . . . . . . . . . . . . . . . . . . . . . . .9 1.4常用算法技术和工具. . . . . . . . . . . . .十1.5旋算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11添加段：auslander - partner算法•添加路径：Hopcroft-Tarjan算法•添加边：de Fraysseix-Ossona de Mendez-Rosenstiehl算法1.6顶点加法算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .leppel - even - cederbaum算法•Shih-Hsu算法•Boyer-Myrvold算法
Roma Tre University 1.1 Properties and Characterizations of Planar Graphs . . . . . 2 Basic Definitions • Properties • Characterizations 1.2 Planarity Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Constrained Planarity • Deletion and Partition Problems • Upward Planarity • Outerplanarity • Simultaneous Planarity • Clustered Planarity 1.3 History of Planarity Algorithms. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Common Algorithmic Techniques and Tools . . . . . . . . . . . . . 10 1.5 Cycle-Based Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Adding Segments: The Auslander-Parter Algorithm • Adding Paths: The Hopcroft-Tarjan Algorithm • Adding Edges: The de Fraysseix-Ossona de Mendez-Rosenstiehl Algorithm 1.6 Vertex Addition Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 The Lempel-Even-Cederbaum Algorithm • The Shih-Hsu Algorithm • The Boyer-Myrvold Algorithm