Recognizing string graphs in NP
Recognizing string graphs in NP
复制标题
DOI：
10.1145/509907.509910
复制
发表时间：
2002-05
期刊：
影响因子：
--
通讯作者：
M. Schaefer;E. Sedgwick;Daniel Stefankovic
中科院分区：
文献类型：
--
作者：
M. Schaefer;E. Sedgwick;Daniel Stefankovic
弦图是平面上一组曲线的交图。每条曲线都由一个顶点表示，两个顶点之间的边意味着相应的曲线相交。我们表明，字符串图可以识别在NP。直到最近，当两篇独立的论文建立了实现字符串图所需的交叉点数量的指数上界时，才知道识别问题是可判定的[18，20]。这些结果表明，识别问题在于NEXP。在本文中，我们通过证明字符串图的识别问题是NP问题，因此是NP-完全的，因为Kratochvíl [12]证明了识别问题是NP-困难的。结果有后果的计算复杂性的问题，在图形绘制和拓扑推理。
A string graph is the intersection graph of a set of curves in the plane. Each curve is represented by a vertex, and an edge between two vertices means that the corresponding curves intersect. We show that string graphs can be recognized in NP. The recognition problem was not known to be decidable until very recently, when two independent papers established exponential upper bounds on the number of intersections needed to realize a string graph [18, 20]. These results implied that the recognition problem lies in NEXP. In the present paper we improve this by showing that the recognition problem for string graphs is in NP, and therefore NP-complete, since Kratochvíl [12] showed that the recognition problem is NP-hard. The result has consequences for the computational complexity of problems in graph drawing, and topological inference.