Obstacle Numbers of Graphs

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
  
  

• Journal Discrete and Computational Geometry
• Online ISSN 1432-0444
• Print ISSN 0179-5376

Published by

Original source : http://www.springerlink.com/content/45038g67t22463...