AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

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. 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 VPG graphs are equivalent to the string 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. 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.

Danny Hermelin

--email hidden

passcode not visible

logged in users only