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. 129-150, 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 Bk-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 well-known class of string graphs, namely, the intersection graphs of arbitrary curves in the plane.
In the case of B0-VPG graphs, we observe that horizontal and vertical
segments have strong Helly number 2, and thus the clique problem has polynomial-time complexity,
given the path representation.
The recognition and coloring problems for B0-VPG graphs, however, are NP-complete.
We give a 2-approximation algorithm for coloring B0-VPG graphs. Furthermore, we prove that triangle-free B0-VPG graphs are 4-colorable, 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 B0-VPG graphs and the circle graphs are strictly contained in B1-VPG.
We prove the strict containment of B0-VPG into B1-VPG,
and we conjecture that, in general, this strict containment continues for all values of k. We present a graph which is not in B1-VPG.
Planar graphs are known to be in the class of string graphs, and we prove here that
planar graphs are B3-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
|