On obstacle numbers
The obstacle number is a new graph parameter introduced by Alpert, Koch, and Laison (2010). Mukkamala et al. (2012) show that there exist graphs with n vertices having obstacle number in Ω(n/ log n). In this note, we up this lower bound to Ω(n/(log log n)<sup>2</sup>). Our proof makes use of an upper bound of Mukkamala et al. on the number of graphs having obstacle number at most h in such a way that any subsequent improvements to their upper bound will improve our lower bound.
|Journal||Electronic Journal of Combinatorics|
Dujmović, V, & Morin, P. (2015). On obstacle numbers. Electronic Journal of Combinatorics, 22(3).
|Publisher's version Final Version|