Grid obstacle representation of graphs

Arijit Bishnu, Arijit Ghosh, Rogers Mathew, Gopinath Mishra, Subhabrata Paul

The grid obstacle representation of a graph $G=(V,E)$ is an injective function $f:V \rightarrow \mathbb{Z}^2$ and a set of point obstacles $\mathcal{O}$ on the grid points of $\mathbb{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 $\mathbb{Z}^2$ avoiding the obstacles of $\mathcal{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 $\mathbb{Z}^3$. We also show NP-hardness result for the point set embeddability of an $\ell_1$-obstacle representation.

picture_as_pdf flag

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment