Obstacle Numbers of Graphs |
| |
Authors: | Hannah Alpert Christina Koch Joshua D Laison |
| |
Institution: | 1. Department of Mathematics, University of Chicago, 5734 S. University Avenue, Chicago, IL, 60637, USA 2. Academy of Hope, 601 Edgewood St. NE, Suite 25, Washington, DC, 20017, USA 3. Mathematics Department, Willamette University, 900 State St., Salem, OR, 97301, USA
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|