On intersection representations of co-planar graphs
On intersection representations of co-planar graphs
复制标题
关于共面图的交表示
DOI：
10.1016/s0012-365x(97)81834-1
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
A. Kuběna
中科院分区：
文献类型：
--
作者：
Jan Kratochvíl;A. Kuběna
我们证明了平面图的补具有平面上凸集的交表示，即对于每一个平面图，可以将平面上的凸集分配给它的顶点，当且仅当对应的顶点相邻时，两个集合是不相交的。这一事实有一个复杂的结果，即确定平面上凸集相交图的团数的问题是np困难的。我们注意到，对于平面上直线段的相交图，这个问题的复杂性是未知的。
We show that complements of planar graphs have intersection representations by convex sets in the plane, i.e., for every planar graph, one can assign convex sets in the plane to its vertices in such a way that two of the sets are disjoint if and only if the correspondning vertices are adjacent. This fact has a complexity consequence — it follows that the problem of determining the clique number of an intersection graph of convex sets in the plane is NP-hard. We note that the complexity of this problem for intersection graphs of straight line segments in the plane is unknown.