Graphs with no grid obstacle representation
Pach, János · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · 2016
A graph G = ( V; E ) admits a grid obstacle representation , if there exist a subset Ω of the planar integer grid Z 2 and an embed- ding f : V ! Z 2 such that no vertex of G is mapped into a point of Ω , and two vertices u; v 2 V are connected by an edge of G if and only if there is a shortest path along the edges of Z 2 that con- nects f ( u ) and f ( v ) and avoids all other elements of Ω [ f ( V ) . We answer a question of Bishnu, Ghosh, Mathew, Mishra, and Paul, by showing that there exist graphs that do not admit a grid obstacle representation.