Graphs with Obstacle Number Greater than One
Leah Wrenn Berman, Glenn G. Chappell, Jill R. Faudree, John Gimbel, Chris Hartman, and Gordon I. Williams
Vol. 21, no. 6, pp. 1107-1119, 2017. Concise paper.
Abstract An obstacle representation of a graph $G$ is a straight-line drawing of $G$ in the plane, together with a collection of connected subsets of the plane, called obstacles, that block all non-edges of $G$ while not blocking any edges of $G$. The obstacle number $\mathrm{obs}(G)$ is the least number of obstacles required to represent $G$. We study the structure of graphs with obstacle number greater than one. We show that the icosahedron has obstacle number $2$, thus answering a question of Alpert, Koch, & Laison asking whether all planar graphs have obstacle number at most $1$. We also show that the $1$-skeleta of two related polyhedra, the gyroelongated $4$-bipyramid and the gyroelongated $6$-bipyramid, have obstacle number $2$. The order of the former graph is $10$, which is also the order of the smallest known graph with obstacle number $2$, making this the smallest known planar graph with obstacle number $2$. Our methods involve instances of the Satisfiability problem; we make use of various "SAT solvers" in order to produce computer-assisted proofs.
Submitted: February 2017.
Reviewed: August 2017.
Revised: September 2017.
Accepted: October 2017.
Final: October 2017.
Published: October 2017.
Communicated by Csaba D. Tóth
article (PDF)