| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420393 | Discrete Applied Mathematics | 2009 | 7 Pages |
We answer some of the questions raised by Golumbic, Lipshteyn and Stern and obtain some other results about edge intersection graphs of paths on a grid (EPG graphs). We show that for any d≥4d≥4, in order to represent every nn vertex graph with maximum degree dd as an edge intersection graph of nn paths on a grid, a grid of area Θ(n2)Θ(n2) is needed. We also show several results related to the classes BkBk-EPG, where BkBk-EPG denotes the class of graphs that have an EPG representation such that each path has at most kk bends. In particular, we prove: For a fixed kk and a sufficiently large nn, the complete bipartite graph Km,nKm,n does not belong to B2m−3B2m−3-EPG (it is known that this graph belongs to B2m−2B2m−2-EPG); for any odd integer kk we have BkBk-EPG ⫋Bk+1⫋Bk+1-EPG; there is no number kk such that all graphs belong to BkBk-EPG; only 2O(knlog(kn))2O(knlog(kn)) out of all the 2n2 labeled graphs with nn vertices are in BkBk-EPG.
