Edge intersection graphs of systems of grid paths with bounded number of bends
Andrei Asinowski, Andrew Suk · 2008
We answer some of the questions raised by Golumbic, Lipshteyn and Stern regarding edge intersection graphs of paths on a grid (EPG graphs). We prove that for any d ≥ 4, in order to represent all n vertex graphs with maximum degree d as edge intersection graphs of n paths, a grid of area �(n 2 ) is needed. A bend is a turn of a path at a grid point. Let Bk be the class of graphs that have an EPG representation such that each path has at most k bends. We show several results related to the classes Bk; among them we prove that for any odd integer k, Bk $ Bk+1. Lastly, we show that only a very small fraction of all the 2 ( n 2 ) labeled graphs on n vertices