论文标题
向上平面的参数化算法
Parameterized Algorithms for Upward Planarity
论文作者
论文摘要
我们获得了新的参数化算法，用于确定有向的无环形图是否允许向上平面图的经典问题。我们的结果包括通过源数量来参数的新的固定参数算法，通过树宽参数为参数的XP-Algorithm以及由Treedepepth参数化的固定参数算法。所有三种算法都是使用新的框架来获得的，该框架将SPQR树分类与参数化技术相结合的问题。我们的方法统一和推动超出了串联挖掘，单源挖掘和外平面挖掘的问题的先前障碍结果。
We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algorithm parameterized by treewidth, and a fixed-parameter algorithm parameterized by treedepth. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Our approach unifies and pushes beyond previous tractability results for the problem on series-parallel digraphs, single-source digraphs and outerplanar digraphs.
