Lower bounds on the obstacle number of graphs

Given a graph G, an obstacle representation of G is a set of points in the plane representing the vertices of G, together with a set of connected obstacles such that two vertices of G are joined by an edge if and only if the corresponding points can be connected by a segment which avoids all obstacles. The obstacle number of G is the minimum number of obstacles in an obstacle representation of G. It is shown that there are graphs on n vertices with obstacle number at least Omega(n/logn).


Published in:
Electronic Journal Of Combinatorics, 19, -
Year:
2012
Keywords:
Laboratories:




 Record created 2012-07-13, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)