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)

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.

[error in script]

IITH Creators:	IITH Creators ORCiD Mathew, Rogers https://orcid.org/0000-0003-4536-1136
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
URI:	http://raiithold.iith.ac.in/id/eprint/9288
Publisher URL:	https://doi.org/10.1016/j.dam.2020.09.027
OA policy:	https://v2.sherpa.ac.uk/id/publication/11425
Related URLs:	Author

Actions (login required)

View Item

Statistics for this ePrint Item