Grid obstacle representation of graphs
share
The grid obstacle representation of a graph G=(V,E) is an injective function f:V →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 ℓ_1-obstacle representation.
READ FULL TEXT