The grid obstacle representation  of a graph G=(V,E) is an injective function f:V \rightarrow Z^2 and a set of point obstacles O on the grid points of Z^2 (where V has not been mapped) such that uv is an edge in G if and only if there exists a Manhattan path between f(u) and f(v) in Z^2 avoiding the obstacles of O . The grid obstacle number of a graph is the smallest number of obstacles needed for the grid obstacle representation of G. This work shows that planar graphs admit such a representation while there exists some non-planar graphs that do not admit such a representation. Moreover, we show that every graph admits  grid obstacle representation in Z^3. We also show NP-hardness result for the point set embeddability of an \ell_1-obstacle representation.
The grid obstacle representation , or alternately, \ell_1-obstacle representation of a graph G=(V,E) is an injective function f:V \rightarrow Z^2 and a set of point obstacles O on the grid points of Z^2 (where no vertex of V has been mapped) such that uv is an edge in G if and only if there exists a Manhattan path between f(u) and f(v) in Z^2 avoiding the obstacles of O and points in f(V). This work shows that planar graphs admit such a representation while there exist some non-planar graphs that do not admit such a representation. Moreover, we show that every graph admits a grid obstacle representation in Z^3. We also show NP-hardness result for the point set embeddability of an \ell_1-obstacle representation.
A
, or alternately, \ell_1-obstacle representation
R
V has not
no vertex of V has
R
. The grid obstacle number of a graph is the smallest number of obstacles needed for the grid obstacle representation of G.
and points in f(V).
R
exists
exist
A
a