Vertex Contact Representations of Paths on a Grid
Vol. 19, no. 3, pp. 817-849, 2015. Regular paper.
Abstract 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 uv 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.
Submitted: March 2015.
Reviewed: July 2015.
Revised: October 2015.
Reviewed: November 2015.
Revised: December 2015.
Accepted: December 2015.
Final: December 2015.
Published: December 2015.
Communicated by Csaba D. Tóth
article (PDF)