Alpha-algorithms for incremental planarity testing (preliminary version)
Alpha-algorithms for incremental planarity testing (preliminary version)
复制标题
用于增量平面度测试的 Alpha 算法（初步版本）
DOI：
--
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
H. L. Poutré
中科院分区：
文献类型：
--
作者：
H. L. Poutré
本文提出了一种用于增量式平面性测试的数据结构。在任何时候，数据结构都可以回答以下类型的查询：给定图中的两个节点，是否可以在这些节点之间插入一条边，以便保留平面性，同时不时插入边（保留平面性）。从n个节点的“空“图开始，数据结构的运行时间为O（n + rn）。a（m，n））次，其中m是查询和边插入的总数。该数据结构还允许插入节点（在相同的时间范围内，将n作为最终节点数），作为一个共同的结果，找到给定（静态）图的最大平面子图的问题可以在O（n + e.a（e，n））时间内解决，其中e是图中的边数。
In this paper, a data structure is presented for incremental planarity testing. At any moment, the data structure can answer the following type of query: given two nodes in the graph, can an edge be inserted between these nodes such that planarity is preserved, while edges (preserving planarity) are inserted from time to time. Starting from an " empty " graph of n nodes, the data structure runs in O (n + rn. a(m, n)) time, where m is the total number of queries and edge insertions. The data structure allows for insertions of nodes also (in the same time bounds, taking n as the final number of nodes), As a co-result, the problem of finding a maximal planar subgraph of a given (static) graph can be solved in O(n + e.a(e, n)) time, where e is the number of edges in the graph.