On Rectilinear and Polar Visibility Graphs
by
Joan P. Hutchinson
Macalester College, St. Paul, MN, USA

Visibility graphs are created by the reasonable placement of reasonable objects in Euclidean space with specified admissible lines of sight between the objects. The objects represent vertices and lines of sight represent edges of a corresponding visibility graph. Two points of view dominate: 1) given a choice of objects and lines of sight, what graphs are so representable? and 2) given a class of graphs can they be represented as visibility graphs and if so, how?

We survey results in three rectilinear models (bar-visibility, rectangle-visibility, and universal 3-dimensional visibility) and in one new model (polar visibility). The former use, respectively, horizontal line segments in the plane with vertical visibility, axis-aligned rectangles in the plane with vertical and horizontal visibility, and convex polygons parallel to the x-y plane in 3-space with z-directional visibility. They represent, respectively, some planar, some thickness-two, and all graphs. In contrast, polar visibility graphs use arcs of concentric circles with radial visibility, including visibility through the origin, representing some graphs embeddable on the real projective plane. We compare characterizations of these classes of graphs and algorithms for their layout, with regard to the applicability and aesthetic appeal of each approach.

Date received: October 6, 2000