Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes

Benjamin Jauregui, Pedro Montealegre, Ivan Rapaport

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 corresp…