Grid Obstacle Representation of Graphs

2017/08/05 by Bishnu, Arijit, Ghosh, Arijit, Mathew, Rogers +2
#05C62 #Computational Geometry (cs.CG) #FOS: Computer and information sciences #I.3.5

paper · doi:10.48550/arxiv.1708.01765

Abstract

The grid obstacle representation, or alternately, ℓ₁-obstacle representation of a graph G=(V,E) is an injective function f:V → ℤ² and a set of point obstacles O on the grid points of ℤ² (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 ℤ² 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 ℤ³. We also show NP-hardness result for the point set embeddability of an ℓ₁-obstacle representation.

Related

• Grid-Obstacle Representations with Connections to Staircase Guarding
• Geodesic Obstacle Representation of Graphs
• Graphs with Plane Outside-Obstacle Representations
• Lower bounds on the obstacle number of graphs
• Outside-Obstacle Representations with All Vertices on the Outer Face