Strip Planarity Testing for Embedded Planar Graphs
Strip Planarity Testing for Embedded Planar Graphs
复制标题
嵌入式平面图的带状平面度测试
作者：
Patrizio Angelini;G. D. Lozzo;G. Battista;Fabrizio Frati
本文介绍并研究了以平面图G(V，E)和函数$$GAMMA：V为输入的带材平面度检验问题
Ightarrow{1，2，dots，k}$$γ：v→{1，2，⋯，k}，并询问是否存在G的平面图，使得G的每条边都由y方向单调的曲线表示，并且对于任何$$u，vin V$$u，v∈V具有$$γ(U)<；Gamma(V)$$γ(U)<；y(V)$$y(U)<；y(V)。这个问题与平面性测试问题中研究最深入的一些变体有很强的关系，如簇状平面性、向上平面性和水平平面性。最值得注意的是，我们提供了从条带平面度测试到聚簇平面度测试的多项式时间缩减。我们证明了，如果G有一个指定的组合嵌入，则带状平面性检验问题是多项式时间可解的。
In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph G(V, E) and a function $$gamma :V
ightarrow {1,2,dots ,k}$$γ:V→{1,2,⋯,k} and asks whether a planar drawing of G exists such that each edge is represented by a curve that is monotone in the y-direction and, for any $$u,vin V$$u,v∈V with $$gamma (u)<gamma (v)$$γ(u)<γ(v), it holds that $$y(u)<y(v)$$y(u)<y(v). The problem has strong relationships with some of the most deeply studied variants of the planarity testing problem, such as clustered planarity, upward planarity, and level planarity. Most notably, we provide a polynomial-time reduction from strip planarity testing to clustered planarity. We show that the strip planarity testing problem is polynomial-time solvable if G has a prescribed combinatorial embedding.