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.
Celestial 4-configurations are a class of highly symmetric geometric configurations of points and lines in the plane in which 4 points lie on each line and 4 lines pass through each point (that is, they are (n4) configurations). The set of isometries of the plane that map a configuration to itself (that is, the symmetries of the configuration) partition the points into orbits, called the symmetry classes of points, and likewise the symmetries of the configuration partition the lines into orbits as well, forming the set of symmetry classes of lines. Celestial 4-configurations have the property that two lines from each of two symmetry classes of lines pass through each point, and two points from each of two symmetry classes of points lie on each line; a celestial 4-configuration with k symmetry classes is called k-celestial. Celestial configurations may be classified as being trivial, systematic, or sporadic. Previously, three non-trivial classes of 3-celestial 4-configurations were known. This paper presents a number of new systematic families of celestial 4-configurations, including 16 new 3-celestial families, four 4-celestial families, and three classes of h-celestial configurations for infinitely many values of h, although it does not provide a complete classification.