On obstacle numbers (Q2517647)

Summary: The obstacle number is a new graph parameter introduced by \textit{H. Alpert} et al. [Discrete Comput. Geom. 44, No. 1, 223--244 (2010; Zbl 1216.05088)]. \textit{P. Mukkamala} et al. [Electron. J. Comb. 19, No. 2, Research Paper P32, 8 p. (2012; Zbl 1243.05176)] show that there exist graphs with \(n\) vertices having obstacle number in \(\Omega(n/\log n)\). In this~note, we up this lower bound to \(\Omega(n/(\log\log n)^2)\). Our proof~makes use of an upper bound of Mukkamala et al. [loc. cit.] 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.