Edge intersection graphs of systems of paths on a grid with a bounded number of bends
2009; Elsevier BV; Volume: 157; Issue: 14 Linguagem: Inglês
10.1016/j.dam.2009.06.015
ISSN1872-6771
Autores Tópico(s)Interconnection Networks and Systems
ResumoWe 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≥4, in order to represent every n vertex graph with maximum degree d as an edge intersection graph of n paths on a grid, a grid of area Θ(n2) is needed. We also show several results related to the classes Bk-EPG, where Bk-EPG denotes the class of graphs that have an EPG representation such that each path has at most k bends. In particular, we prove: For a fixed k and a sufficiently large n, the complete bipartite graph Km,n does not belong to B2m−3-EPG (it is known that this graph belongs to B2m−2-EPG); for any odd integer k we have Bk-EPG ⫋Bk+1-EPG; there is no number k such that all graphs belong to Bk-EPG; only 2O(knlog(kn)) out of all the 2n2 labeled graphs with n vertices are in Bk-EPG.
Referência(s)