Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00454-009-9233-8 | Discrete & Computational Geometry |
Keywords | Field | DocType |
Obstacle number,Convex obstacle number,Circular arc graph,Proper circular arc graph,Non-double-covering circular arc graph,Interval bigraph,Visibility graph | Discrete mathematics,Topology,Obstacle,Block graph,Combinatorics,Line graph,Crossing number (graph theory),Visibility graph,Circular-arc graph,Mathematics,Planar graph,Complement graph | Journal |
Volume | Issue | ISSN |
44 | 1 | 0179-5376 |
Citations | PageRank | References |
10 | 0.81 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hannah Alpert | 1 | 16 | 3.47 |
| Christina Koch | 2 | 14 | 2.21 |
| Joshua D. Laison | 3 | 38 | 7.08 |