On-Line Planar Graph Embedding
On-Line Planar Graph Embedding
复制标题
在线平面图嵌入
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
R. Tamassia
中科院分区：
文献类型：
--
作者：
R. Tamassia
我们提出了一个动态的数据结构的增量建设的平面图的平面嵌入。数据结构支持以下操作：（i）测试是否可以在不引入交叉的情况下将新的边添加到嵌入;以及（ii）添加顶点和边。每个操作的时间复杂度为O（logn）（为边插入摊销），存储空间和预处理时间为O（n），其中是图的当前顶点数。
We present a dynamic data structure for the incremental construction of a planar embedding of a planar graph. The data structure supports the following operations: (i) testing if a new edge can be added to the embedding without introducing crossing; and (ii) adding vertices and edges. The time complexity of each operation isO(logn) (amortized for edge insertion), and the memory space and preprocessing time areO(n), wherenis the current number of vertices of the graph.