Name
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 $${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: 10.1007/s00454-009-9233-8, 2009). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00373-011-1027-0 | Graphs and Combinatorics |
Keywords | Field | DocType |
polygonal obstacle,bipartite graph,total number,obstacle number,small graph,graph g,fixed integer h,large obstacle number,extremal graph theoretic tool,smallest number,low obstacle number,enumeration,visibility graph | Topology,Discrete mathematics,Combinatorics,Indifference graph,Graph toughness,Graph homomorphism,Chordal graph,Bipartite graph,Independent set,1-planar graph,Triangle-free graph,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 3 | 1435-5914 |
Citations | PageRank | References |
8 | 0.87 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Pach | 1 | 2366 | 292.28 |
| Deniz Sarioz | 2 | 34 | 5.24 |