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. 11071119, 2017. Concise paper.
Abstract An obstacle representation of a graph $G$
is a straightline drawing of $G$ in the plane,
together with a collection of connected subsets of the plane,
called obstacles, that block all nonedges
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
computerassisted 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

Journal Supporters
