Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00380
Vertex Contact Representations
of Paths on a Grid
Vol. 19, no. 3, pp. 817849, 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 gridpaths on a square grid. Adjacencies are represented by contacts between an endpoint of one gridpath and an interior point of another gridpath. 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 2orientation α and a flow ψ in the angle graph. The 2orientation describes the contacts of the ends of a gridpath and the flow describes the behavior of a gridpath 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 4bend representation and simple planar (2,0)sparse graphs have 6bend 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

Journal Supporters
