ABSTRACT
A graph G is an edge intersection graph of paths on a grid (or EPG graph), edge intersection graph of paths on a grid EPG graph if its vertices can be represented as simple paths on a rectangular grid, such that two vertices are adjacent in the graph, if and only if their corresponding paths share at least one edge of the grid. Formally, we state this as follows:
