On Obstacle Numbers
Copyright policy )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 $\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.
- Carleton University Canada
- University of Ottawa Canada
Computational Geometry (cs.CG), FOS: Computer and information sciences, Extremal problems in graph theory, Discrete Mathematics (cs.DM), Graph representations (geometric and intersection representations, etc.), FOS: Mathematics, Mathematics - Combinatorics, Computer Science - Computational Geometry, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, Extremal problems in graph theory, Discrete Mathematics (cs.DM), Graph representations (geometric and intersection representations, etc.), FOS: Mathematics, Mathematics - Combinatorics, Computer Science - Computational Geometry, Combinatorics (math.CO), Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).8 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!