%0 Journal Article
%T Lower bounds on the obstacle number of graphs
%A Padmini Mukkamala
%A J¨¢nos Pach
%A D£¿m£¿t£¿r P¨¢lv£¿lgyi
%J Computer Science
%D 2011
%I arXiv
%X Given a graph $G$, an {\em 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 {\em 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})$.
%U http://arxiv.org/abs/1103.2724v1