Grid obstacle representation of graphs

Bishnu, A. and Mathew, R. and et al, . (2021) Grid obstacle representation of graphs. Discrete Applied Mathematics, 296. pp. 39-51. ISSN 0166218X

Full text not available from this repository. (Request a copy)


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.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Mathew, Rogers
Item Type: Article
Uncontrolled Keywords: Geometric graph, Grid obstacle representation, Obstacle number
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Mrs Haseena VKKM
Date Deposited: 07 Jun 2022 06:39
Last Modified: 07 Jun 2022 06:39
Publisher URL:
OA policy:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 9288 Statistics for this ePrint Item