\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P32}{19(2)}{2012}

\usepackage{fullpage}   % uncomment if you want
\usepackage{authblk}    % needed for \affil
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsthm}
\usepackage{graphicx, hyperref}
\usepackage{fixmath}
\usepackage{tikz}
\usepackage{subfigure}
\usepackage{mathptmx}      % use Times fonts if available on your TeX system

% use this command to create hyperlinks (optional and recommended)
%\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\definecolor{temp}{rgb}{1,0,0}
\newcommand{\uj}{\color{temp}}

%\include{./mathdefs.harvard}

\theoremstyle{plain}
\newtheorem{theorem*}{Theorem}%[section]
\newtheorem{claim*}[theorem*]{Claim}
\newtheorem{corollary*}[theorem*]{Corollary}
\newtheorem{lemma*}[theorem*]{Lemma}

\title{\bf Lower bounds on the obstacle number of graphs
\thanks{The authors gratefully acknowledge support
from the Bernoulli Center at EPFL and from the Swiss National
Science Foundation, Grant No. 200021-125287/1. Research by the
second author was also supported by grants from NSF, NSA, and
OTKA. Research by the second and third author was also supported
by EUROGIGA project GraDR 10-EuroGIGA-OP-003 (OTKA NN 102029).}}

\author{Padmini Mukkamala\\
\small McDaniel College\\%[-0.8ex] 
\small Budapest, Hungary\\
\small\tt padmini.mvs@gmail.com\\
\and
J{\'{a}}nos Pach\\
\small Ecole Polytechnique F\'ed\'erale de Lausanne\\%[-0.8ex] 
\small Lausanne, Switzerland\\
\small\tt pach@cims.nyu.edu
\and
D\"om\"ot\"or P\'alv\"olgyi\\
\small E\"otv\"os University\\%[-0.8ex] 
\small Budapest, Hungary\\
\small\tt dom@cs.elte.hu
}

\date{\dateline{Mar 9, 2011}{May 23, 2012}{Jun 6, 2012}\\
\small Mathematics Subject Classifications: 05C62, 68R10}

\begin{document}

\maketitle

\begin{abstract}
%:abstract
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})$.

\bigskip\noindent \textbf{Keywords:} Obstacle number, visibility graph, graph representation

%\keywords{Obstacle number \and visibility graph \and hereditary graph property \and forbidden induced subgraphs \and split graphs \and enumeration}
%%05-XX             Combinatorics For finite fields, see 11Txx
%%  05Cxx       Graph theory
%05C62 %    Graph representations (geometric and intersection representations, etc.) For graph drawing, see also 68R10
%05C75 %    Structural characterization of families of graphs
%% 05C85 %      Graph algorithms % decided not to
%68R10 % computer science :: Discrete mathematics in relation to computer science :: graph theory (including graph drawing)
%\subclass{05C62, 05C75, 68R10}
\end{abstract}

\section{Introduction}


Consider a set $P$ of points in the plane and a set of closed
polygonal obstacles whose vertices together with the points in $P$
are in {\em general position}, that is, no {\em three} of them are
on a line. The corresponding {\em visibility graph} has $P$ as its
vertex set, two points $p,q\in P$ being connected by an edge if
and only if the segment $pq$ does not meet any of the obstacles.
Visibility graphs are extensively studied and used in
computational geometry, robot motion planning, computer vision,
sensor networks, etc.; see \cite{BKOS00}, \cite{G07}, \cite{OR97},
\cite{O99}, \cite{Ur00}.

Alpert, Koch, and Laison \cite{AKL09} introduced an interesting
new parameter of graphs, closely related to visibility graphs.
Given a graph $G$, we say that a set of points and a set of
polygonal obstacles as above constitute an {\em obstacle
representation} of $G$, if the corresponding visibility graph is
isomorphic to $G$. A representation with $h$ obstacles is also
called an $h$-obstacle representation. The smallest number of
obstacles in an obstacle representation of $G$ is called the {\em
obstacle number} of $G$ and is denoted by ${\rm obs}(G)$. Alpert
et al. \cite{AKL09} proved that there exist graphs with
arbitrarily large obstacle numbers.

Using tools from extremal graph theory, it was shown in \cite{PS}
that for any fixed $h$, the number of graphs with obstacle number
at most $h$ is $2^{o(n^2)}$. Notice that this immediately implies
the existence of graphs with arbitrarily large obstacle numbers.

In the present note, we establish some more precise estimates.

\begin{theorem*}\label{enumeration}
 (i) For any positive integer $h$, the number of graphs on $n$
(labeled) vertices that admit a representation with $h$ obstacles
is at most $$2^{O(hn log^2 n)}.$$
                  (ii) Moreover, the number of graphs on $n$ (labeled)
vertices that admit a representation with a set of obstacles
having a total of $s$ sides, is at most $$2^{O(n log n + s log
s)}.$$
\end{theorem*}

In the above bounds, it makes no difference whether we count
labeled or unlabeled graphs, because the number of labeled graphs
is at most $n!=2^{O(n log n)}$  times the number of unlabeled
ones.

It follows from Theorem~\ref{enumeration} (i) that for every $n$,
there exists a graph $G$ on $n$ vertices with obstacle number
$${\rm obs}(G)\geq \Omega\left({n}/{\log^2n}\right).$$
Indeed, as long as $2^{O(hn\log^2n)}$ is smaller than
$2^{\Omega(n^2)}$, the total number of (labeled) graphs with $n$
vertices, we can find at least one graph on $n$ vertices with
obstacle number $h$.

Here we show the following slightly stronger bound.

\begin{theorem*}\label{concave}
For every $n$, there exists a graph $G$ on $n$ vertices with
obstacle number
$${\rm obs}(G)\geq \Omega\left({n}/{\log n}\right).$$
\end{theorem*}

This comes close to answering the question in \cite{AKL09} whether
the obstacle number of every graph with $n$ vertices is at most
$O(n)$. However, we have no upper bound on the maximum obstacle
number of $n$-vertex graphs, better than $O(n^2)$. In fact, we
conjecture that the truth is somewhere around $n^2$.

Our next theorem answers another question from \cite{AKL09}.

\begin{theorem*}\label{exactly}
For every $h$, there exists a graph with obstacle number exactly
$h$.
\end{theorem*}


A special instance of the obstacle problem has received a lot of
attention, due to its connection to the Szemer\'edi-Trotter
theorem on incidences between points and lines~\cite{ST83a},
\cite{ST83b}, and other classical problems in incidence
geometry~\cite{PA95}. This is to decide whether the obstacle
number of ${\overline{K}}_n$, the empty graph on $n$ vertices, is
$O(n)$ if the obstacles must be {\em points}. This question is
commonly called ``the blocking conjecture''; for related problems,
see the survey by  P{\'o}r and Wood~\cite{PW10}. The best known
upper bound is $n2^{O(\sqrt{\log n})}$ is due to Pach
\cite{Pach03} (see also Dumitrescu et al.~\cite{DPT09}, Matou\v
sek~\cite{M09}, Aloupis et al. \cite{A+10conf}, and
Stanchescu~\cite{ST} for a related result), while a superlinear
lower bound is conjectured by most experts.

It is an interesting open problem to decide whether the obstacle
number of planar graphs can be bounded from above by a constant.
For outerplanar graphs, one obstacle is enough, as shown in
\cite{AKL09}. Fulek, Saeedi, and Sar{\i}\"oz~\cite{FSS} have also
proved that every outerplanar graph has a representation with at
most five {\em convex} obstacles.

Theorem $i$ is proved in Section $i+1,\; 1\le i\le 3$.



\section{Proof of Theorem \ref{enumeration}}\label{sec:convex}
We will prove the theorem by a simple counting method.
Before turning to the proof, we
introduce some terminology. Given any placement (embedding) of the
vertices of $G$ in general position in the plane, a {\em straight-line drawing} or, in short, a {\em drawing}
of $G$ consists of the image of the embedding and the set of {\em
open line segments} connecting all pairs of points that correspond to the edges of $G$. If there is no danger of confusion, we make no
notational difference between the vertices of $G$ and the
corresponding points, and between the pairs $uv$ and the
corresponding open segments. The complement of the set of all
points that correspond to a vertex or belong to at least one edge
of $G$ falls into connected components. These components are
called the {\em faces} of the drawing. Notice that if $G$ has an
obstacle representation with a particular placement of its vertex
set, then

(1) each obstacle must lie entirely in one face of the drawing,
and

(2) each non-edge of $G$ must be blocked by at least one of the
obstacles.\\


We start by proving a result about the {\em convex obstacle number}
(a special case of Theorem \ref{concave}), as the arguments are
simpler here. Then we tackle Theorem \ref{enumeration} using similar methods.

Following Alpert et al., we define the {\em convex
obstacle number} ${\rm obs}_c(G)$  of a
graph $G$ as the minimal number of obstacles in an obstacle
representation of $G$, in which each obstacle is convex.

\begin{claim*}\label{convex}
For every $n$, there exists a graph $G$ on $n$ vertices with
convex obstacle number
$${\rm obs}_c(G)\geq \Omega\left({n}/{\log n}\right).$$
\end{claim*}

The idea is to find a short encoding of the obstacle
representations of graphs, and to use this to give an upper bound
on the number of graphs with low obstacle number. The proof uses
the concept of order types. Two sets of points, $P_1$ and $P_2$,
in general position in the plane are said to have the same {\em
order type} if there is a one to one correspondence between them
with the property that the orientation of any triple in $P_1$ is
the same as the orientation of the corresponding triple in $P_2$.
Counting the number of different order types is a classical task.

\medskip
\noindent {\bf Theorem A.} [Goodman, Pollack~\cite{GP86}] {\em
The number of different order types of $n$ points in general
position in the plane is $2^{O(n\log n)}$. }\medskip

\noindent Observe that asymptotically the same upper bound holds for the number
of different order types of $n$ {\em labeled} points, because the
number of different permutations of $n$ points is $n!=2^{O(n\log
n)}$.

\begin{proof}[Proof of Claim~\ref{convex}]
We will give an upper bound for the number of graphs that admit a
representation with at most $h$ convex obstacles. Let us fix such
a graph $G$, together with a representation. Let $V$ be the set of
points representing the vertices, and let $O_1,\ldots, O_h$ be the
convex obstacles. For any obstacle $O_i$, rotate an oriented
tangent line $\ell$ along its boundary in the clockwise direction.
We can assume without loss of generality that $\ell$ never passes
through two points of $V$. Let us record the sequence of points
met by $\ell$. If $v\in V$ is met at the right side of $\ell$, we
add the symbol $v^+$ to the sequence, otherwise we add $v^-$. (See
Figure 1.)%\ref{fig:convex}.)


% Figure by Padmini
\begin{figure*}[ht]
\label{fig:convex}
{\centering
\subfigure[Empty]{
\begin{tikzpicture}[scale=0.35]
\filldraw [blue!80!black!20!white] (0,0) -- (1,1) -- (2.5,1) -- (3.5,0) -- (2.5,-1) -- (1,-1) -- (0,0) -- cycle;
\node [fill=black,circle,inner sep=1pt,label=left:$1$] (1) at (-1,0) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$2$] (2) at (2,3) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$3$] (3) at (3,-2.5) {}; 
\draw [<-,red] (0,4) -- (0,-3);
\draw [->,green] (-0.5,4) arc (145:35:22pt);
\end{tikzpicture}
}
\qquad
\subfigure[$2^+$]{
\begin{tikzpicture}[scale=0.35]
\filldraw [blue!80!black!20!white] (0,0) -- (1,1) -- (2.5,1) -- (3.5,0) -- (2.5,-1) -- (1,-1) -- (0,0) -- cycle;
\node [fill=black,circle,inner sep=1pt,label=left:$1$] (1) at (-1,0) {}; 
\node [fill=red,circle,inner sep=1pt,label=left:$2$] (2) at (2,3) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$3$] (3) at (3,-2.5) {}; 
\draw [->,red] (-2,-3) -- (2.5,3.75);
\end{tikzpicture}
}
\qquad
\subfigure[$2^+1^-$]{
\begin{tikzpicture}[scale=0.35]
\filldraw [blue!80!black!20!white] (0,0) -- (1,1) -- (2.5,1) -- (3.5,0) -- (2.5,-1) -- (1,-1) -- (0,0) -- cycle;
\draw [->,red] (-1.75,-0.375) -- (3.75,2.375);
\node [fill=red,circle,inner sep=1pt,label=left:$1$] (1) at (-1,0) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$2$] (2) at (2,3) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$3$] (3) at (3,-2.5) {}; 
\end{tikzpicture}
}
\qquad
\subfigure[$2^+1^-2^-$]{
\begin{tikzpicture}[scale=0.35]
\filldraw [blue!80!black!20!white] (0,0) -- (1,1) -- (2.5,1) -- (3.5,0) -- (2.5,-1) -- (1,-1) -- (0,0) -- cycle;
\node [fill=black,circle,inner sep=1pt,label=left:$1$] (1) at (-1,0) {}; 
\node [fill=red,circle,inner sep=1pt,label=left:$2$] (2) at (2,3) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$3$] (3) at (3,-2.5) {}; 
\draw [->,red] (1.5,4) -- (5,-3);
\end{tikzpicture}
}
\qquad
\subfigure[$2^+1^-2^-3^+$]{
\begin{tikzpicture}[scale=0.35]
\filldraw [blue!80!black!20!white] (0,0) -- (1,1) -- (2.5,1) -- (3.5,0) -- (2.5,-1) -- (1,-1) -- (0,0) -- cycle;
\node [fill=black,circle,inner sep=1pt,label=left:$1$] (1) at (-1,0) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$2$] (2) at (2,3) {}; 
\node [fill=red,circle,inner sep=1pt,label=left:$3$] (3) at (3,-2.5) {}; 
\draw [<-,red] (2.75,-3.75) -- (4.25,3.75);
\end{tikzpicture}
}
\qquad
\subfigure[$2^+1^-2^-3^+1^+$]{
\begin{tikzpicture}[scale=0.35]
\filldraw [blue!80!black!20!white] (0,0) -- (1,1) -- (2.5,1) -- (3.5,0) -- (2.5,-1) -- (1,-1) -- (0,0) -- cycle;
\node [fill=red,circle,inner sep=1pt,label=left:$1$] (1) at (-1,0) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$2$] (2) at (2,3) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$3$] (3) at (3,-2.5) {}; 
\draw [<-,red] (-2,0.5) -- (4.5,-2.75);
\end{tikzpicture}
}
\qquad
\subfigure[$2^+1^-2^-3^+1^+3^-$]{
\begin{tikzpicture}[scale=0.35]
\filldraw [blue!80!black!20!white] (0,0) -- (1,1) -- (2.5,1) -- (3.5,0) -- (2.5,-1) -- (1,-1) -- (0,0) -- cycle;
\node [fill=black,circle,inner sep=1pt,label=left:$1$] (1) at (-1,0) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$2$] (2) at (2,3) {}; 
\node [fill=red,circle,inner sep=1pt,label=left:$3$] (3) at (3,-2.5) {}; 
\draw [<-,red] (-1.5,0.875) -- (5,-4);
\end{tikzpicture}
}
\qquad
\subfigure[$2^+1^-2^-3^+1^+3^-$]{
\begin{tikzpicture}[scale=0.35]
\filldraw [blue!80!black!20!white] (0,0) -- (1,1) -- (2.5,1) -- (3.5,0) -- (2.5,-1) -- (1,-1) -- (0,0) -- cycle;
\node [fill=black,circle,inner sep=1pt,label=left:$1$] (1) at (-1,0) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$2$] (2) at (2,3) {}; 
\node [fill=black,circle,inner sep=1pt,label=left:$3$] (3) at (3,-2.5) {}; 
\draw (3,-2.5) -- (-1,0) -- (2,3);
\draw [dashed,red](3,-2.5) -- (2,3);
\node (4) at (5,0) {};
\end{tikzpicture}
}
\caption{Parts (a) to (g) show the construction of the sequence and (h) shows the visibilities. The arrow on the tangent line indicates the direction from the point of tangency in which we assign $+$ as a label to the vertex. The additional arrow in (a) indicates that the tangent line is rotated clockwise around the obstacle.}
} 
\end{figure*}


When $\ell$ returns to its initial position, we stop. The
resulting sequence consists of $2n$ characters. From this
sequence, it is easy to reconstruct which pairs of vertices are
visible in the presence of the single obstacle $O_i$. Hence,
knowing these sequences for every obstacle $O_i$, completely
determines the visibility graph $G$. The number of distinct
sequences assigned to a single obstacle is at most $(2n)!$, so the
number of graphs with convex obstacle number at most $h$ cannot
exceed $((2n)!)^h<(2n)^{2hn}$. As long as this number is
smaller than $2^{n\choose 2}$, there is a graph with convex
obstacle number larger than $h$.
\end{proof}

To prove Theorem \ref{enumeration}, we will need one more result.
Given a drawing of a graph, the \emph{complexity} of a face is the number of line-segment sides bordering it. The following result was
proved by Arkin, Halperin, Kedem, Mitchell, and Naor (see Matou\v
sek, Valtr~\cite{MV97} for its sharpness).

\medskip
\noindent {\bf Theorem B.} [Arkin et al.~\cite{AHK95}] {\em
The complexity of a single face in a drawing of a graph with $n$
vertices is at most $O(n\log n)$. }
\medskip

\noindent Note that this bound does not depend on the number of
edges of the graph.

\begin{proof}[Proof of Theorem~\ref{enumeration}] First we show how
to reduce part (i) of the theorem to part (ii). For each graph $G$
with $n$ vertices that admits a representation with at most $h$
obstacles, fix such a representation. Consider the visibility
graph $G$ of the vertices in this representation. As explained at
the beginning of this section, each obstacle belongs to a single
face in this drawing. In view of Theorem~B, the complexity of
every face is $O(n\log n)$. Replacing each obstacle by a slightly
shrunken copy of the face containing it, we can achieve that every
obstacle {\em is} a polygonal region with $O(n\log n)$ sides. We
have $\log (hn\log n)=O(\log n)$, since $h\le {n\choose 2}$, so we
are done.

Next we prove part (ii). Notice that the order type of the
sequence $S$ starting with the vertices of $G$, followed by the
vertices of the obstacles (listed one by one, in cyclic order, and
properly separated from one another), completely determines $G$.
That is, we have a sequence of length $N$ with $N\le n + s$.
According to Theorem~A (and the comment following it), the number
of different order types with this many points is at most
$$2^{O(N\log N)}<2^{c(n+s)\log (n+s)},$$
for a suitable constant $c>0$. This is a very generous upper
bound: most of the above sequences do not correspond to any
visibility  graph $G$.
\end{proof}

Following Alpert et al., we define the {\em segment obstacle number} ${\rm obs}_s(G)$ of a graph $G$ as the minimal number of obstacles in an obstacle representation of $G$, in which each obstacle is a
{\em (straight-line) segment}. If we only allow segment obstacles, we have $s=2n$, and thus Theorem \ref{enumeration} (ii) implies the following bound.

\begin{corollary*}\label{segment}
For every $n$, there exists a graph $G$ on $n$ vertices with
segment obstacle number
$${\rm obs}_s(G)\geq \Omega\left({n^2}/{\log n}\right).$$
\end{corollary*}

In general, as long as the sum of the sides of the obstacles, $s$,
satisfies $s\log s=o({n\choose 2})$, we can argue that there is a
graph that cannot be represented with such obstacles.




\section{Proof of Theorem \ref{concave}}\label{sec:concave}

Before turning to the proof, we need a simple property of obstacle representations.

\begin{lemma*}\label{lemma}
Let $k>0$ be an integer and let $G$ be a graph with $n$ vertices that has an obstacle representation with fewer than $\frac{n}{2k}$ obstacles. Then $G$ has at least $\lfloor\frac{n}{2k}\rfloor$ vertex disjoint induced subgraphs of $k$ vertices with obstacle number at most one.
\end{lemma*}

\begin{proof}
Fix an obstacle representation of $G$ with fewer than $\frac{n}{2k}$
obstacles. Suppose without loss of generality that in this representation no two vertices have the same $x$-coordinate. Using vertical lines, divide the vertices of $G$ into $\lfloor\frac{n}{k}\rfloor$ groups of size $k$ and possibly a last group that contains fewer than $k$ vertices. Let $G_1, G_2, \ldots$ denote the subgraphs of $G$ induced by these groups. Notice that if the convex hull of the vertices of $G_i$ does not entirely contain an obstacle, then ${\rm obs}(G_i)\le 1$. Therefore, the number of subgraphs $G_i$ that have $k$ points and obstacle number at most one is larger than $\lfloor\frac{n}{k}\rfloor - \frac{n}{2k}$, and the lemma is true.
\end{proof}

We prove Theorem \ref{concave} by a probabilistic argument.

\begin{proof}[Proof of Theorem \ref{concave}]
Let $G$ be a random graph on $n$ labeled vertices, whose edges are chosen independently with probability 1/2. Let $k$ be a positive integer to be specified later. According to Lemma~\ref{lemma},
$${\mbox{\rm Prob}}[{\rm obs}(G)<n/(2k)]$$
can be estimated from above by the probability that $G$ has at least
$\lfloor\frac{n}{2k}\rfloor$ vertex disjoint induced subgraphs of $k$ vertices such that each of them has obstacle number at most one. Let $p(n,k)$ denote the probability that $G$ satisfies this latter condition.

Suppose that $G$ has $\lfloor n/(2k)\rfloor$ vertex disjoint induced subgraphs $G_1, G_2,\ldots$ with $|V(G_i)|=k$ and ${\rm obs}(G_i)\le 1$. The vertices of $G_1, G_2,\ldots$ can be chosen in
at most ${n\choose k}^{\lfloor n/(2k)\rfloor}$ different ways. It follows from Theorem~\ref{enumeration}(i) that the probability that  a fixed $k$-tuple of vertices in $G$ induces a subgraph with obstacle number at most one is at most
$$2^{O(k\log^2k)-{k\choose 2}}.$$
For disjoint $k$-tuples of vertices, the events that the obstacle numbers of their induced subgraphs do not exceed one are independent.

Therefore, we have
$$p(n,k)\le  {n\choose k}^{\lfloor n/(2k)\rfloor}\cdot
(2^{O(k\log^2k)-{k\choose 2}})^{\lfloor n/(2k)\rfloor}\le
2^{n\log n - nk/4 + O(n\log^2k)}.$$
Setting $k=\lfloor 5\log n\rfloor)$, the right-hand side of the last inequality tends to zero. In this case, almost all graphs on $n$ vertices have obstacle number at least $\frac{n}{2k}>\frac{n}{10\log n}$, which completes the proof.
\end{proof}


\section{Proof of Theorem \ref{exactly}}\label{sec:exactly}
Alpert, Koch, and Laison \cite{AKL09} asked whether for every natural number $h$ there exists a graph whose obstacle number is exactly $h$. Here we answer this question in the affirmative.

\begin{proof}[Proof of Theorem \ref{exactly}]
Pick a graph $G$ with obstacle number $h'>h$. (The existence of
such a graph was first proved in \cite{AKL09}, but it also follows
from Theorem \ref{concave}.) Let $n$ denote the number of
vertices of $G$. Consider the complete graph $K_n$ on $V(G)$. Clearly, ${\rm obs}(K_n)=0$, and $G$ can be obtained from $K_n$
by successively deleting edges. Observe that as we delete an edge
from a graph $G'$, its obstacle number cannot increase by more
than {\em one}. Indeed, if we block the deleted edge $e$ by adding a very small obstacle that does not intersect any other edge of $G'$, we obtain a valid obstacle representation of $G'-e$. (Of course, the obstacle number of a graph can also {\em decrease} by the removal of an edge.) At the beginning of the process, $K_n$ has obstacle number {\em zero}, at the end $G$ has obstacle number $h'>h$, and whenever it increases, the increase is {\em one}. We can conclude that at some stage we obtain a graph with obstacle number precisely $h$.
\end{proof}

The same argument applies to the convex obstacle number, to the
segment obstacle number, and many similar parameters.


\subsection*{Acknowledgement.}

We are indebted to Den{\.{i}}z Sar{\i}{\"{o}}z for many valuable
discussions on the subject.
We would also like to thank the anonymous referees for their comments.
A conference version containing some
results from this paper and some from \cite{PS} appeared in
\cite{MPS}.


%\nocite{*}
\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{A+10conf}
Greg Aloupis, Brad Ballinger, Sebastien Collette, Stefan Langerman, Attila
  P\'or, and David~R. Wood.
\newblock Blocking coloured point sets.
\newblock In J\'anos Pach, editor, {\em Thirty Essays in Geometric Graph
  Theory}, Algorithms and Combinatorics Series. Springer, 2012.

\bibitem{AKL09}
Hannah Alpert, Christina Koch, and Joshua~D. Laison.
\newblock Obstacle numbers of graphs.
\newblock {\em Discrete {\&} Computational Geometry}, 44(1):223--244, 2010.

\bibitem{AHK95}
Esther~M. Arkin, Dan Halperin, Klara Kedem, Joseph S.~B. Mitchell, and Nir
  Naor.
\newblock Arrangements of segments that share endpoints: single face results.
\newblock {\em Discrete \& Computational Geometry}, 13(3-4):257--270, 1995.

\bibitem{BKOS00}
Mark de~Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf.
\newblock {\em Computational Geometry. Algorithms and Applications (2nd ed.)}.
\newblock Springer-Verlag, Berlin, 2000.

\bibitem{DPT09}
Adrian Dumitrescu, J{\'a}nos Pach, and G{\'e}za T\'oth.
\newblock A note on blocking visibility between points.
\newblock {\em Geombinatorics}, 19(1):67--73, 2009.

\bibitem{FSS}
Radoslav Fulek, Den{\.{i}}z Sar{\i}{\"{o}}z, and Noushin Saeedi.
\newblock Convex obstacle number of outerplanar graphs and bipartite
  permutation graphs.
\newblock In J\'anos Pach, editor, {\em Thirty Essays in Geometric Graph
  Theory}, Algorithms and Combinatorics Series. Springer, 2012.

\bibitem{G07}
Subir~Kumar Ghosh.
\newblock {\em Visibility algorithms in the plane}.
\newblock Cambridge University Press, Cambridge, 2007.

\bibitem{GP86}
Jacob~E. Goodman and Richard Pollack.
\newblock Upper bounds for configurations and polytopes in {${\bf R}^d$}.
\newblock {\em Discrete Comput. Geom.}, 1(3):219--227, 1986.

\bibitem{MV97}
Jir\'{\i} Matou{\v{s}}ek and Pavel Valtr.
\newblock The complexity of lower envelope of segments with $h$ endpoints.
\newblock {\em Intuitive Geometry, Bolyai Society of Math. Studies},
  6:407--411, 1997.

\bibitem{M09}
Ji\v{r}\'{\i} Matou\v{s}ek.
\newblock Blocking visibility for points in general position.
\newblock {\em Discrete \& Computational Geometry}, 42(2):219--223, 2009.

\bibitem{MPS}
Padmini Mukkamala, J{\'a}nos Pach, and Deniz Sari{\"o}z.
\newblock Graphs with large obstacle numbers.
\newblock In Dimitrios~M. Thilikos, editor, {\em WG}, volume 6410 of {\em
  Lecture Notes in Computer Science}, pages 292--303, 2010.

\bibitem{OR97}
Joseph O'Rourke.
\newblock Visibility.
\newblock In {\em Handbook of discrete and computational geometry}, CRC Press
  Ser. Discrete Math. Appl., pages 467--479. CRC, Boca Raton, FL, 1997.

\bibitem{O99}
Joseph O'Rourke.
\newblock Open problems in the combinatorics of visibility and illumination.
\newblock In {\em Advances in discrete and computational geometry ({S}outh
  {H}adley, {MA}, 1996)}, volume 223 of {\em Contemp. Math.}, pages 237--243.
  Amer. Math. Soc., Providence, RI, 1999.

\bibitem{Pach03}
J{\'a}nos Pach.
\newblock Midpoints of segments induced by a point set.
\newblock {\em Geombinatorics}, 13(2):98--105, 2003.

\bibitem{PA95}
J{\'a}nos Pach and Pankaj~K. Agarwal.
\newblock {\em Combinatorial geometry}.
\newblock Wiley-Interscience Series in Discrete Mathematics and Optimization.
  John Wiley \& Sons Inc., New York, 1995.
\newblock A Wiley-Interscience Publication.

\bibitem{PS}
J{\'a}nos Pach and Deniz Sari{\"o}z.
\newblock On the structure of graphs with low obstacle number.
\newblock {\em Graphs and Combinatorics}, 27(3):465--473, 2011.

\bibitem{PW10}
Attila P{\'o}r and David~R. Wood.
\newblock On visibility and blockers.
\newblock {\em J. Comput. Geom.}, 1(1):29--40, 2010.

\bibitem{ST}
Yonutz~V. Stanchescu.
\newblock Planar sets containing no three collinear points and non-averaging
  sets of integers.
\newblock {\em Discrete Math.}, 256(1-2):387--395, September 2002.

\bibitem{ST83b}
Endre Szemer{\'e}di and William~T. Trotter, Jr.
\newblock A combinatorial distinction between the {E}uclidean and projective
  planes.
\newblock {\em European J. Combin.}, 4(4):385--394, 1983.

\bibitem{ST83a}
Endre Szemer{\'e}di and William~T. Trotter, Jr.
\newblock Extremal problems in discrete geometry.
\newblock {\em Combinatorica}, 3(3-4):381--392, 1983.

\bibitem{Ur00}
Jorge Urrutia.
\newblock Art gallery and illumination problems.
\newblock In {\em Handbook of computational geometry}, pages 973--1027.
  North-Holland, Amsterdam, 2000.

\end{thebibliography}

\end{document}
