The Complexity of Upward Drawings on Spheres
The Complexity of Upward Drawings on Spheres
复制标题
球体向上绘图的复杂性
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
A. Kisielewicz
中科院分区：
文献类型：
--
作者：
S. M. Hashemi;I. Rival;A. Kisielewicz
虽然有一个线性时间算法来判定一个有序集是否有一个拓扑上等价于一个球面的表面上的向上的绘图，我们将证明，一个有序集是否有一个向上的绘图的球面上的决策问题是NP-完全的。证明涉及调查的表面拓扑结构的有序集突出，特别是他们的鞍点。它与最近由A. Garg和R. Tamassia（1995）认为向上平面性测试是NP完全的，对此我们给出了新的证明。
Although there is a linear time algorithm to decide whether an ordered set has an upward drawing on a surface topologically equivalence to a sphere, we shall prove that the decision problem whether an ordered set has an upward drawing on a sphere is NP-complete. The proof involves the investigation of the surface topology of ordered sets highlighting especially their saddle points. It echoes the recent, important result due to A. Garg and R. Tamassia (1995) that upward planarity testing is NP-complete, for which we give a new proof.