On Obstacle Numbers

  • Vida Dujmović Department of Computer Science and Electrical Engineering, University of Ottawa
  • Pat Morin School of Computer Science, Carleton University

Abstract

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 $\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. 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.

Published
2015-07-01
Article Number
P3.1