On the Structure of Graphs with Low Obstacle Number |
| |
Authors: | J��nos Pach Deniz Sar??z |
| |
Institution: | 1. ??cole Polytechnique F??d??rale de Lausanne, Station 8, 1015, Lausanne, Switzerland 2. The Graduate Center of the City University of New York, 365 Fifth Avenue, New York, NY, 10016, USA
|
| |
Abstract: | 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 Pr?mel, Steger, Bollobás, 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 2o(n2){2^{o(n^2)}}. This implies that there are bipartite graphs with arbitrarily large obstacle number, which answers a question of Alpert
et al. (Discret Comput Geom doi:, 2009). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|