Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs

Details Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs

2011-04-24

arxiv.org/abs/1104.4656v3

Computer Science

Discrete Mathematics

11 pages, 6 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convex obstacle numbers of outerplanar graphs and bipartite permutation graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-544383