Vertex Contact Graphs of Paths on a Grid

Contact and intersection representations of graphs and particularly of planar graphs have been studied for decades. The by now best known result in the area may be the Koebe-Andreev-Thurston circle packing theorem. A more recent highlight in the area is a result of Chalopin and Gonçalves: every planar graph is an intersection graph of segments in the plane. This boosted the study of intersection and contact graphs of restricted classes of curves. In this paper we study planar graphs that are VCPG, i.e. graphs admitting a representation as Vertex Contact graph of Paths on a Grid. In such a representation the vertices of G are represented by a family of interiorly disjoint grid-paths. Adjacencies are represented by contacts between an endpoint of one grid-path and an interior point of another grid-path. Defining u → v if the path of u ends on path of v we obtain an orientation on G from a VCPG representation. To get hand on the bends of the grid path the 2-orientation is not enough. We therefore consider pairs (α,ψ): a 2-orientation α and a flow ψ in the angle graph. The 2-orientation describes the contacts of the ends of a grid-path and the flow describes the behavior of a grid-path between its two ends. We give a necessary and sufficient condition for such a pair (α,ψ) to be realizable as a VCPG. Using realizable pairs we show that every planar (2,2)-tight graph can be represented with at most 2 bends per path and that this is tight (i.e. there exist (2,2)-tight graphs that cannot be represented with at most one bend per path). Using the same methodology it is easy to show that loopless planar (2,1)-sparse graphs have a 4-bend representation and loopless planar (2,0)-sparse graphs have 6-bend representation. We do not believe that the latter two are tight, we conjecture that loopless planar (2,0)-sparse graphs have a 3-bend representation.