Testing Planarity of Partially Embedded Graphs
Testing Planarity of Partially Embedded Graphs
复制标题
测试部分嵌入图的平面性
DOI：
10.1145/2629341
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Ignaz Rutter
中科院分区：
文献类型：
--
作者：
Patrizio Angelini;Giuseppe Di Battista;Fabrizio Frati;Vít Jelínek;Jan Kratochvíl;Maurizio Patrignani;Ignaz Rutter
本文研究如下问题：给定一个平面图G和G的一个子图的平面图（嵌入），这样的图能不能推广到整个图G的平面图？这个问题符合将问题的部分解扩展为完整解的范式，这在许多不同的设置中已经被研究过。与许多情况下，在输入中的部分解决方案的存在下，否则很容易的问题很难，我们表明，平面性问题仍然是多项式时间可解的。我们的算法是基于几个组合引理，这表明部分嵌入图的平面性表现出“TONCAS”行为“的平面性的明显的必要条件也是充分的。这些条件是用（1）循环之间的旋转系统和包含关系与（2）图分解为连通、双连通和三连通分量之间的相互作用来表示的。这意味着决策算法不需要动态规划，分解的元素可以独立处理。此外，通过为分解的组件配备合适的数据结构，并通过仔细地将问题分解为更简单的子问题，我们使我们的算法在线性时间内运行。最后，我们考虑了问题的几个推广，例如最小化需要重新路由以扩展它的部分嵌入的边的数量，并认为它们是NP难的。我们还将我们的算法同时图形绘制问题同步嵌入固定边（Sefe）。在那里，我们得到一个线性时间算法的情况下，输入图或公共图有一个固定的平面嵌入。
We study the following problem: given a planar graphGand a planar drawing (embedding) of a subgraph ofG, can such a drawing be extended to a planar drawing of the entire graphG? This problem fits the paradigm of extending a partial solution for a problem to a complete one, which has been studied before in many different settings. Unlike many cases, in which the presence of a partial solution in the input makes an otherwise easy problem hard, we show that the planarity question remains polynomial-time solvable. Our algorithm is based on several combinatorial lemmas, which show that the planarity of partially embedded graphs exhibits the ‘TONCAS’ behavior “the obvious necessary conditions for planarity are also sufficient.” These conditions are expressed in terms of the interplay between (1) the rotation system and containment relationships between cycles and (2) the decomposition of a graph into its connected, biconnected, and triconnected components. This implies that no dynamic programming is needed for a decision algorithm and that the elements of the decomposition can be processed independently.Further, by equipping the components of the decomposition with suitable data structures and by carefully splitting the problem into simpler subproblems, we make our algorithm run in linear time.Finally, we consider several generalizations of the problem, such as minimizing the number of edges of the partial embedding that need to be rerouted to extend it, and argue that they are NP-hard. We also apply our algorithm to the simultaneous graph drawing problemSimultaneous Embedding with Fixed Edges (Sefe). There we obtain a linear-time algorithm for the case that one of the input graphs or the common graph has a fixed planar embedding.
登录
查看更多内容
用于增量平面度测试的 Alpha 算法（初步版本）
DOI：
--
发表时间：
1994
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
H. L. Poutré
通讯作者：
H. L. Poutré
图算法与应用杂志 具有很少弯曲的平面图的同时嵌入
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
C. Erten;S. Kobourov
通讯作者：
S. Kobourov
图算法与应用杂志 固定边同时嵌入中的相交图
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
M. Jünger;M. Schulz;S. Kobourov;M. Jünger;M. Schulz
通讯作者：
M. Schulz
在线平面图嵌入
DOI：
--
发表时间：
1996
期刊：
J. Algorithms
影响因子：
--
作者：
R. Tamassia
通讯作者：
R. Tamassia
同时嵌入具有固定边的图
DOI：
--
发表时间：
2006
期刊：
International Symposium Graph Drawing and Network Visualization
影响因子：
--
作者：
Fabrizio Frati
通讯作者：
Fabrizio Frati