Given a graph $G$, an obstacle representation of $G$ is a set of points in the plane representing the vertices of $G$, together with a set of connected obstacles such that two vertices of $G$ are joined by an edge if and only if the corresponding points can be connected by a segment which avoids all obstacles. The obstacle number of $G$ is the minimum number of obstacles in an obstacle representation of $G$. It is shown that there are graphs on $n$ vertices with obstacle number at least $\Omega({n}/{\log n})$.
@article{10_37236_2380,
author = {Padmini Mukkamala and J\'anos Pach and D\"om\"ot\"or P\'alv\"olgyi},
title = {Lower bounds on the obstacle number of graphs},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {2},
doi = {10.37236/2380},
zbl = {1243.05176},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2380/}
}
TY - JOUR
AU - Padmini Mukkamala
AU - János Pach
AU - Dömötör Pálvölgyi
TI - Lower bounds on the obstacle number of graphs
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2380/
DO - 10.37236/2380
ID - 10_37236_2380
ER -
%0 Journal Article
%A Padmini Mukkamala
%A János Pach
%A Dömötör Pálvölgyi
%T Lower bounds on the obstacle number of graphs
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2380/
%R 10.37236/2380
%F 10_37236_2380
Padmini Mukkamala; János Pach; Dömötör Pálvölgyi. Lower bounds on the obstacle number of graphs. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2380
