Obstacle number of planar graphs

Recomm. for undergrads: yes
Posted by: Andrew King
on: November 23rd, 2011

Does there exist a planar graph with obstacle number greater than 1? Is there some $k$ such that every planar graph has obstacle number at most $k$?

A $k$-obstacle drawing of a graph $G$ is a mapping of the vertices of $G$ to points in the plane, along with a set of polygonal obstacles $P_1,\ldots, P_k$, such that two vertices are adjacent precisely if the line segment connecting their corresponding points in $\mathbb R^2$ does not intersect any obstacle. The {\em obstacle number} of a graph $G$ is the minimum $k$ such that $G$ has a $k$-obstacle drawing.

This invariant was recently introduced by Alpert, Koch, and Laison [AKL], who proved that every outerplanar graph has obstacle number 1. The next question, then, follows naturally: what is the obstacle number of a planar graph? So far no planar graph has been proved to have obstacle number greater than 1. Alpert, Koch, and Laison specifically ask what the obstacle numbers of the icosahedron and dodecahedron are [AKL].

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries) [AKL] Hannah Alpert, Christina Koch, and Joshua D. Laison: Obstacle numbers of graphs. Discrete Comput. Geom. (2010) 44:223-244.

* indicates original appearance(s) of problem.