Abstract An obstacle representation of a graph
G is a drawing of
G in the plane with straight-line edges, together with a set of polygons (respectively, convex polygons) called obstacles,
such that an edge exists in
G if and only if it does not intersect an obstacle. The obstacle number (convex obstacle number) of
G is the smallest number of obstacles (convex obstacles) in any obstacle representation of
G. In this paper, we identify families of graphs with obstacle number 1 and construct graphs with arbitrarily large obstacle
number (convex obstacle number). We prove that a graph has an obstacle representation with a single convex
k-gon if and only if it is a circular arc graph with clique covering number at most
k in which no two arcs cover the host circle. We also prove independently that a graph has an obstacle representation with
a single segment obstacle if and only if it is the complement of an interval bigraph.
- Content Type Journal Article
- DOI 10.1007/s00454-009-9233-8
- Authors
- Hannah Alpert, University of Chicago Department of Mathematics 5734 S. University Avenue Chicago IL 60637 USA
- Christina Koch, Academy of Hope 601 Edgewood St. NE, Suite 25 Washington DC 20017 USA
- Joshua D. Laison, Willamette University Mathematics Department 900 State St. Salem OR 97301 USA
