The grid obstacle representation of a graph $G=(V,E)$ is an injectivefunction $f:V ightarrow mathbb{Z}^2$ and a set of point obstacles$mathcal{O}$ on the grid points of $mathbb{Z}^2$ (where $V$ has not beenmapped) such that $uv$ is an edge in $G$ if and only if there exists aManhattan path between $f(u)$ and $f(v)$ in $mathbb{Z}^2$ avoiding theobstacles of $mathcal{O}$. The grid obstacle number of a graph is the smallestnumber of obstacles needed for the grid obstacle representation of $G$. Thiswork shows that planar graphs admit such a representation while there existssome non-planar graphs that do not admit such a representation. Moreover, weshow that every graph admits grid obstacle representation in $mathbb{Z}^3$. Wealso show NP-hardness result for the point set embeddability of an$ell_1$-obstacle representation.
展开▼
