Header menu link for other important links
X
Grid obstacle representation of graphs
A. Bishnu, A. Ghosh, , G. Mishra, S. Paul
Published in Elsevier B.V.
2021
Volume: 296
   
Pages: 39 - 51
Abstract
The grid obstacle representation, or alternately, ℓ1-obstacle representation of a graph G=(V,E) is an injective function f:V→Z2 and a set of point obstacles O on the grid points of Z2 (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 Z2 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 Z3. We also show NP-hardness result for the point set embeddability of an ℓ1-obstacle representation. © 2020 Elsevier B.V.
About the journal
JournalData powered by TypesetDiscrete Applied Mathematics
PublisherData powered by TypesetElsevier B.V.
ISSN0166218X