Name
Abstract | ||
|---|---|---|
The disjoint convex obstacle number of a graph G is the smallest number h such that there is a set of h pairwise disjoint convex polygons (obstacles) and a set of n points in the plane (corresponding to V(G)) so that a vertex pair uv is an edge if and only if the corresponding segment uv does not meet any obstacle. We show that the disjoint convex obstacle number of an outerplanar graph is always at most 5, and of a bipartite permutation graph at most 4. The former answers a question raised by Alpert, Koch, and Laison. We complement the upper bound for outerplanar graphs with the lower bound of 4. |
Year | Venue | Keywords |
|---|---|---|
2011 | Clinical Orthopaedics and Related Research | upper bound,outerplanar graph,computational geometry,discrete mathematics,permutation graph,lower bound |
Field | DocType | Volume |
Permutation graph,Discrete mathematics,Combinatorics,Disjoint sets,Bound graph,Bipartite graph,Cograph,Pathwidth,1-planar graph,Mathematics,Planar graph | Journal | abs/1104.4 |
Citations | PageRank | References |
4 | 0.45 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Radoslav Fulek | 1 | 125 | 22.27 |
| Noushin Saeedi | 2 | 6 | 1.85 |
| Deniz Sarioz | 3 | 34 | 5.24 |