Map graphs in polynomial time
Map graphs in polynomial time
复制标题
多项式时间内绘制图表
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
M. Thorup
中科院分区：
文献类型：
--
作者：
M. Thorup
Z. Chen等人（1997，1998）引入了平面性的修改概念，其中两个面被认为是相邻的，如果它们共享至少一个点。对应的抽象图称为映射图。Chen等人提出了映射图是否可以在多项式时间内识别的问题。他们证明了决策问题是NP问题，并给出了一个多项式时间算法的特殊情况下，我们允许最多4个面相交于任何点，只有3个被允许相交于一个点，我们得到通常的平面图。Chen等人证明了映射图可以在多项式时间内被识别，本文肯定地解决了他们的猜想。
Z. Chen et al. (1997, 1998) have introduced a modified notion of planarity, where two faces are considered adjacent if they share at least one point. The corresponding abstract graphs are called map graphs. Chen et al. raised the question of whether map graphs can be recognized in polynomial time. They showed that the decision problem is in NP and presented a polynomial time algorithm for the special case where we allow at most 4 faces to intersect in any point-for only 3 are allowed to intersect in a point, we get the usual planar graphs. Chen et al. conjectured that map graphs can be recognized in polynomial time, and in this paper, their conjecture is settled affirmatively.