Paper Info
Title
Bend-bounded path intersection graphs: sausages, noodles, and waffles on a grill
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 Bk-VPG. We show here that for every fixed k, Bk-VPG $\subsetneq$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.
Year
DOI
Venue
2012
10.1007/978-3-642-34611-8_28
workshop on graph-theoretic concepts in computer science
Keywords
DocType
Volume
graphs representable,rectangular grid,inclusion relation,1-vpg representation,bend-bounded path intersection graph,class bk-vpg,k-bend path,straight line segment,input graph,fixed k,intersection graph
Conference
abs/1206.5159
ISSN
Citations 
PageRank 
0302-9743
7
0.60
References 
Authors
14
4
Name
Order
Citations
PageRank
steven chaplick17616.91
Vít Jelínek214920.45
Jan Kratochvíl31751151.84
tomas vyskocil4565.61