Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00452
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)
BibTeX