Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00253
Vertex Intersection Graphs of Paths on a Grid
Andrei Asinowski,
Elad Cohen,
Martin Charles Golumbic,
Vincent Limouzy,
Marina Lipshteyn, and
Michal Stern
Vol. 16, no. 2, pp. 129150, 2012. Regular paper.
Abstract We investigate the class of vertex intersection graphs of paths on a grid, and specifically
consider the subclasses that are obtained when each path in the representation has at most
k bends (turns). We call such a subclass the B_{k}VPG graphs, k ≥ 0.
In chip manufacturing, circuit layout is modeled as paths (wires) on a grid, where it is natural
to constrain the number of bends per wire for reasons of feasibility and to reduce the cost
of the chip.
If the number k of bends is not restricted, then the VPG graphs are equivalent to the wellknown class of string graphs, namely, the intersection graphs of arbitrary curves in the plane.
In the case of B_{0}VPG graphs, we observe that horizontal and vertical
segments have strong Helly number 2, and thus the clique problem has polynomialtime complexity,
given the path representation.
The recognition and coloring problems for B_{0}VPG graphs, however, are NPcomplete.
We give a 2approximation algorithm for coloring B_{0}VPG graphs. Furthermore, we prove that trianglefree B_{0}VPG graphs are 4colorable, and this is best possible.
We present a hierarchy of VPG graphs relating them to other known families of graphs.
The grid intersection graphs
are shown to be equivalent to the bipartite B_{0}VPG graphs and the circle graphs are strictly contained in B_{1}VPG.
We prove the strict containment of B_{0}VPG into B_{1}VPG,
and we conjecture that, in general, this strict containment continues for all values of k. We present a graph which is not in B_{1}VPG.
Planar graphs are known to be in the class of string graphs, and we prove here that
planar graphs are B_{3}VPG graphs, although it is not known if this is best possible.

Submitted: December 2010.
Reviewed: September 2011.
Revised: October 2011.
Reviewed: October 2011.
Revised: November 2011.
Accepted: November 2011.
Final: December 2011.
Published: January 2012.
Communicated by
Tandy Warnow

Journal Supporters
