| Tartalmi leírás: |
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.
|
