Publication at Faculty of Mathematics and Physics |
2012
Abstract
In this paper, we study properties of intersection graphs of k- bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns.
The class of graphs representable by intersections of k-bend paths is denoted by B(k)-VPG. We show here that for every fixed k, B(k) -VPG is a strict subset of B(k+1) -VPG and that recognition of graphs from B(k) -VPG is NP-complete even when the input graph is given by a B(k+1)-VPG representation.
We also show that the class B(k) -VPG (for k at least 1) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.