A graph $G=(V,E)$ is a geometric intersection graph if every node $v \in V$ is identified with a geometric object of some particular type, and two nodes are adjacent if the corresponding objects intersect. Geometric intersection graph classes have been studied from both the theoretical and practical point of view. On the one hand, many hard problems can be efficiently solved or approximated when the input graph is restricted to a geometric intersection class of graphs. On the other hand, these graphs appear naturally in many applications such as sensor networks, scheduling problems, and others. Recently, in the context of distributed certification and distributed interactive proofs, the recognition of graph classes has started to be intensively studied. Different results related to the recognition of trees, bipartite graphs, bounded diameter graphs, triangle-free graphs, planar graphs, bounded genus graphs, $H$-minor free graphs, etc., have been obtained. The goal of the present work is to design efficient distributed protocols for the recognition of relevant geometric intersection graph classes, namely permutation graphs, trapezoid graphs, circle graphs, and polygon-circle graphs. More precisely, for the two first classes, we give proof labeling schemes recognizing them with logarithmic-sized certificates. For the other two classes, we give three-round distributed interactive protocols that use messages and certificates of size $\mathcal{O}(\log n)$. Finally, we provide logarithmic lower-bounds on the size of the certificates on the proof labeling schemes for the recognition of any of the aforementioned geometric intersection graph classes.
翻译:图形 $G= (V, E) 是一个几何交叉点图, 如果每个节点 $v\ in V$ 被识别为某特定类型的几何对象, 并且如果对应对象相交, 两个节点是相邻的。 已经从理论和实践角度研究了几何交叉图类 。 一方面, 当输入图限于几何交叉图表时, 许多难题可以有效解决或大致解决。 另一方面, 这些图表自然出现在许多应用程序中, 如传感器网络、 调度问题等 。 最近, 在分布式的认证和分布式交互式校对中, 图形类的识别已经开始深入研究。 不同的结果涉及到树的识别、 双叶图、 直径图、 无三角图、 捆绑式的基因图、 $H$$- minoror 等等。 目前工作的目标是设计有效的分布式协议, 用于识别相关的交互式图表类, 即 透度图表、 深色图、 更深色图的证书, 我们通过两个图表的图表, 向其它图表的排序提供。