Graphs with obstacle number greater than one

DOI10.7155/JGAA.00452MaRDI QIDQ5371041zbMATH OpenOpenAlexFDO

Authors Glenn G. Chappell, Chris Hartman, Leah Wrenn Berman, J. R. Faudree, John Gimbel, Gordon Williams

Publication date 24 October 2017

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1606.03782

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: An emph{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 emph{obstacles}, that block all non-edges of $G$ while not blocking any of the edges of $G$. The emph{obstacle number} obs$(G)$ is the minimum 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$-skeleton of a related polyhedron, the emph{gyroelongated $4$-dipyramid}, has obstacle number $2$. The order of this graph is $10$, which is also the order of the smallest known graph with obstacle number $2$. Some of our methods involve instances of the Satisfiability problem, we make use of various "SAT solvers" in order to produce computer-assisted proofs.

Recommendations

• Graphs with large obstacle numbers
• Lower bounds on the obstacle number of graphs
• On the structure of graphs with low obstacle number

Cited in

(4)

• Geodesic obstacle representation of graphs
• Obstructing visibilities with one obstacle
• Geodesic obstacle representation of graphs
• Outside-obstacle representations with all vertices on the outer face

This page was built for publication: Graphs with obstacle number greater than one

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5371041)