论文标题
重新路由平面曲线和不相交路径
Rerouting Planar Curves and Disjoint Paths
论文作者
论文摘要
在本文中，我们考虑了图表中$ K $分离路径的转换。对于图形和一对$ k $分离路径$ \ MATHCAL {p} $和$ \ MATHCAL {q} $连接相同终端对的集合，我们旨在确定$ \ nathcal {p} $是否可以通过$替换$的路径，因此可以将$替换为$ k，因此，是否可以将$ \ mathcal {q} $转换为$ k.该问题称为不相交路径重新配置。我们首先表明，即使$ k = 2 $，脱节路径重新配置也是pspace complete。另一方面，我们证明，当图将图嵌入到平面上时，所有路径$ \ MATHCAL {P} $和$ \ MATHCAL {Q} $连接两个面的边界时，可以在多义时时间溶解重新配置。该算法基于使用代数相交编号在平面上重新布线曲线的拓扑表征。我们还将不连接$ s $ - $ t $路径的转换视为一种变体。我们表明，可以在多项式时间内确定平面图中的脱节$ S $ - $ t $路径重新配置问题，而该问题通常是PSPACE完成的。
In this paper, we consider a transformation of $k$ disjoint paths in a graph. For a graph and a pair of $k$ disjoint paths $\mathcal{P}$ and $\mathcal{Q}$ connecting the same set of terminal pairs, we aim to determine whether $\mathcal{P}$ can be transformed to $\mathcal{Q}$ by repeatedly replacing one path with another path so that the intermediates are also $k$ disjoint paths. The problem is called Disjoint Paths Reconfiguration. We first show that Disjoint Paths Reconfiguration is PSPACE-complete even when $k=2$. On the other hand, we prove that, when the graph is embedded on a plane and all paths in $\mathcal{P}$ and $\mathcal{Q}$ connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint $s$-$t$ paths as a variant. We show that the disjoint $s$-$t$ paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.
