Graphs with Large Obstacle Numbers

摘要

Motivated by questions in computer vision and sensor networks, Alpert et al. [3] introduced the following definitions. Given a graph G, an obstacle repre-sentation 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 an 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 was shown in [3] that there exist graphs of n vertices with obstacle number at least Ω(logn~1/2). We use extremal graph theo-retic tools to show that (1) there exist graphs of n vertices with obstacle number at least Ω(n/log~2 n), and (2) the total number of graphs on n vertices with bounded obstacle number is at most 2~o(n~2). Better results are proved if we are allowed to use only convex obstacles or polygonal obstacles with a small number of sides.