Simple Geometrical Intersection Graphs
Simple Geometrical Intersection Graphs
复制标题
简单的几何交集图
DOI：
10.1007/978-3-540-77891-2_3
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Ryuhei Uehara
中科院分区：
文献类型：
--
作者：
Ryuhei Uehara
图G = （V， E）当且仅当存在一组对象，使得V中的每个顶点V对应于对象Ov和{u， V}∈E，当且仅当Ov与Ou有非空交，我们称其为相交图。区间图是典型的交点图类，由于其结构简单，许多难题在区间图上变得容易而得到了广泛的研究。本文综述了已知的结果，研究了自然广义区间图的一种（单位）网格相交图。我们证明了图类具有如此丰富的结构，以至于一些典型问题仍然很难在图类上解决。
A graph G = (V, E) is said to be an intersection graph if and only if there is a set of objects such that each vertex v in V corresponds to an object Ov and {u, v} ∈ E if and only if Ov and Ou have a nonempty intersection. Interval graphs are typical intersection graph class, and widely investigated since they have simple structures and many hard problems become easy on the graphs. In this paper, we survey known results and investigate (unit) grid intersection graphs, which is one of natural generalized interval graphs. We show that the graph class has so rich structure that some typical problems are still hard on the graph class.