$\newcommand{\N}{\mathbb{N}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{E}$

$\DeclareMathOperator{\obs}{obs}\DeclareMathOperator{\cupdotop}{\dot{\cup}}$For a set $P\subset \R^2$ of points and a set $R$ of connected subsets of $\R^2$, the visibility graph $V_R(P)$ of $P$ with respect to $R$ is the graph $G=(P,E)$ in which an edge $uw$ is in $E$ if and only the segment with endpoints $u$ and $w$ is disjoint from every element in $R$. We say that $(P,R)$ is an obstacle representation of $G$. The obstacle number, $\obs(G)$ of a graph $G$ is the minimum number of obstacles in any obstacle representation of a graph isomorphic to $G$.

What is the maximum obstacle number of an $n$-vertex graph?

It is known that there are $n$-vertex graphs with obstacle number $\Omega(n/(\log\log n)^2)$ (see Dujmović and Morin) and that every $n$-vertex graph has obstacle number $O(n\log n)$ (see Balko, Cibulka, and Valtr). The lower bound is non-constructive; it shows that a random graph has high obstacle number with high probability.

Give an explicit construction of a graph with large obstacle number.

The upper bound of $O(n\log n)$ starts by placing the vertices of $G$ in general position, but in such a way that there is a set $B$ of $O(n\log n)$ $\epsilon$-disk points that block every pair of vertices. (A disk $D$ blocks $u$ and $w$ if $x$ is in the interior of the line segment joining $u$ and $w$.) Then, a careful perturbation of the vertices is used so that each set of edges that passes through a disk $D\in B$ becomes (in the neighbourhood of $D$) an arrangement of lines in which all lines are incident to one face. In this way, a single obstacle near $D$ is sufficient to block any subset of the edges that passes through $D$.

If we take the limit as $\epsilon\rightarrow 0$, then we obtain a point set that can be blocked by $O(n\log n)$ points. If we want to improve this upper bound, then a natural place to start is to find a set of $n$ points that can be blocked by $o(n\log n)$ points. This is already an open problem (see Conjecture 3 of Pór and Wood).

What is the fewest number of blockers required to block an $n$-point set in general position?

Pinchasi conjectured that the answer is $\Omega(n\log n)$. An upper bound of $n2^{O(\sqrt{n})}$ is due to Pach, who actually shows gives an example of an $n$-point set in general position that has only $n2^{O(\sqrt{n})}$ midpoints. (See my open problems on blockers and midpoints.)

The construction of Balko, Cibulka, and Valtr doesn’t given an $O(n\log n)$ upper bound because, in the limit $\epsilon=0$, the point set stops being in general position (it lives on two vertical lines). This leads to another variant of the blocking question.

Let $S:(0,1]\to(\R^2)^n$ be a continuous family of $n$ point sets with the property that, for all $\epsilon\in(0,1]$, $S(\epsilon)$ is in general position and can be blocked by a set of $f(n)$ $\epsilon$-disks. What is the minimum value of $f(n)$?.

A solution to the preceding problem would not necessarily help with the obstacle number question, unless it has some special structure.

Counting $h$-Obstacle Graphs

What is the number of graphs with obstacle number $h$?

Theorem 1 of Mukkamala et al gives an upper bound of $2^{O(hn\log^2 n)}$. Theorem 4 in Balko, Cibulka, and Valtr gives a lower bound of $2^{\Omega(hn)}$.

Obstacle Numbers of Product Graphs

The product graph $G_1\times G_2$ of two graphs $G_1$ and $G_2$ is the graph with vertex set $V(G_1)\times V(G_2)$ and that contains an edge joing $(u_1,u_2)$ to $(w_1,w_2)$ if $u_1w_1\in E(G_1)$ or $u_2w_2\in E(G_2)$.

What can we say about $\obs(G_1\times G_2)$ in terms of $\obs(G_1)$ and $\obs(G_2)$?

Planar Graphs

Less is known about obstacle numbers of planar graphs:

What is the maximum obstacle number of an $n$-vertex planar graph?

A lower bound of 2 was recently shown by Berman et al, who showed that the icosahedron (as well as another planar graph with 10 vertices) has obstacle number 2. An upper bound of $O(n)$ comes from the fact that a planar drawing of an $n$-vertex planar graph has at most $2n-4$ faces and placing an obstacle inside each face gives an obstacle representation of this graph. Actually, this bound has been reduced to $n-3$ by Gimble etal. The bound of $n-3$ is tight for planar representations of planar graphs.

Gimble etal also show that if $G$ is bipartite and planar, then $\obs(G)\le 1$. This makes it plausible that planar graphs have bounded obstacle number.

Sparse graphs

The known graphs with large obstacle number (namely $G_{n,1/2}$) are dense. If we can’t find planar graphs with large obstacle number, then maybe we can find other sparse graphs with large obstacle number:

Is there a constant $d$ such that $d$-degenerate graphs have arbitrarily large obstacle number?

A Lemma

An outside obstacle in an obstacle representation $(P,R)$ is an obstacle that is not bounded by visibility edges, i.e, there is a path from the obstacle to infinity that does not intersect any edge of $V_R(P)$. An outside obstacle representation of $G$ is an obstacle representation of $G$ that has an outside obstacle. The outside obstacle number of $G$ is the minimum number of obstacles in any outside obstacle representation of $G$.

Here’s a lemma that might help that might be helpful for solving these kinds of problems. (It’s an easy generalization of Lemma 4.1 in Berman etal’s paper).

If $G_1$ and $G_2$ each have outside obstacle number $k$, then their disjoint union, $G=G_1\cupdotop G_2$ has obstacle number $k$.

Observe that $\obs(G_1)\ge k-1$ since, otherwise, we could add a useless outside obstacle to an obstacle representation of $G_1$ with less than $k-1$ obstacles to show that the outside obstacle number of $G_1$ is less than $k$. Also $\obs(G) > \obs(G_1)$ since any obstacle representation of $G$ gives an obstacle representation of $G_1$ just by deleting vertices of $G_2$.

Therefore, the only concern is that $G$ has an obstacle representation with $k-1$ obstacles and that these are all inner obstacles. Take any line, $\ell$ tangent to the convex hull, $C$, of these obstacles. Then the same argument used in Lemma 4.1 of Berman et al’s paper shows that $G_1$ and $G_2$ each contain vertices on both sides of $\ell$. But this is contradiction, since there is some pair of vertices $u\in V(G_1)$ and $w\in V(G_2)$ that are on the side $\ell$ that does not contain $C$. These vertices are not blocked by any obstacle but they are not adjacent in $G$, so this is not an obstacle representation of $G$.

Since the disjoint union of planar graphs is also planar, the preceding lemma reduces the problem of finding graphs with obstacle number $k$ to the problem of finding graphs with outside obstacle number $k$.