Vertex Contact Representations of Paths on a Grid

Nieke Aerts ; Stefan Felsner

Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 3, pp. 817-849.

Résumé

We study Vertex Contact representations of Paths on a Grid (VCPG). In such a representation, the vertices of G are represented by a family of interiorly disjoint grid-paths on a square grid. 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 the path of v, we obtain an orientation on G from a VCPG. To control the bends of the grid paths the 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 admits a VCPG with at most 2 bends per path and that this bound is tight. In a similar way, we show that simple planar (2,1)-sparse graphs have a 4-bend representation and simple planar (2,0)-sparse graphs have 6-bend representation.

Détail

DOI : 10.7155/jgaa.00380