On the Structure of Graphs with Low Obstacle Number

The obstacle number of a graph G is the smallest number of polygonal obstacles in the plane with the property that the vertices of G can be represented by distinct points such that two of them see each other if and only if the corresponding vertices are joined by an edge. We list three small graphs that require more than one obstacle. Using extremal graph theoretic tools developed by Promel, Steger, Bollobas, Thomason, and others, we deduce that for any fixed integer h, the total number of graphs on n vertices with obstacle number at most h is at most 2(0(n2)). This implies that there are bipartite graphs with arbitrarily large obstacle number, which answers a question of Alpert et al. (Discret Comput Geom doi:10.1007/s00454-009-9233-8 Address="10.1007/s00454-009-9233-8" , 2009).

Published in:
Graphs And Combinatorics, 27, 465-473
Presented at:
Japan Conference on Computational Geometry and Graphs (JCCGG2009), Kanazawa, JAPAN, Nov 11-13, 2009

 Record created 2012-01-12, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)