Thumbnail
Access Restriction
Open

Author Chaplick, Steven
Source CiteSeerX
Content type Text
Publisher Springer
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Description 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 Bk-VPG. We show here that for every fixed k, Bk-VPG ( Bk+1-VPG and that recognition of graphs from Bk-VPG is NP-complete even when the input graph is given by a Bk+1-VPG representation. We also show that the class Bk-VPG (for k ≥ 1) is in no inclusion relation with the class of intersection graphs of straight line segments in the plane.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2012-01-01
Publisher Institution IN GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG’12