Planar Straight Line Graphs:Introduction and Features of PSLGs

Introduction

Graphs (Chapter 4) have found extensive applications in computer science as a modeling tool. In mathematical terms, a graph is simply a collection of vertices and edges. Indeed, a popular graph data structure is the adjacency lists representation [14] in which each vertex keeps a list of vertices connected to it by edges. In a typical application, the vertices model entities and an edge models a relation between the entities corresponding to the edge endpoints. For example, the transportation problem calls for a minimum cost shipping pattern from a set of origins to a set of destinations [2]. This can be modeled as a complete directed bipartite graph. The origins and destinations are represented by two columns of vertices. Each origin vertex is labeled with the amount of supply stored there. Each destination vertex is labeled with the amount of demand required there. The edges are directed from the origin vertices to the destination vertices and each edge is labeled with the unit cost of transportation. Only the adjacency information between vertices and edges are useful and captured, apart from the application dependent information.

In geometric computing, graphs are also useful for representing various diagrams. We restrict our attention to diagrams that are planar graphs embedded in the plane using straight edges without edge crossings. Such diagrams are called planar straight line graphs and denoted by PSLGs for short. Examples include Voronoi diagrams, arrangements, and triangulations. Their definitions can be found in standard computational geometry texts such as the book by de Berg et al. [3]. See also Chapters 62, 63 and 64. For completeness, we also provide their definitions in section 17.8. The straight edges in a PSLG partition the plane into regions with disjoint interior. We call these regions faces. The adjacency lists representation is usually inadequate for applications that manipulate PSLGs. Consider the problem of locating the face containing a query point in a Delaunay triangulation. One practical algorithm is to walk towards the query point from a randomly chosen starting vertex [11], see Figure 17.1.

To support this algorithm, one needs to know the first face

that we enter as well as the next face that we step into whenever we cross an edge. Such information is not readily provided by an adjacency lists representation.

There are three well-known data structures for representing PSLGs: the winged-edge, half edge, and quad edge data structures. In Sections 17.2 and 17.3, we discuss the PSLGs that we deal with in more details and the operations on PSLGs. Afterwards, we introduce the three data structures in Section 17.4–17.6. We conclude in Section 17.7 with some further remarks.

Features of PSLGs

We assume that each face has exactly one boundary and we allow dangling edges on a face boundary. These assumptions are valid for many important classes of PSLGs such as triangulations, Voronoi diagrams, planar subdivisions with no holes, arrangements of lines, and some special arrangements of line segments (see Figure 17.2).

There is at least one unbounded face in a PSLG but there could be more than one, for example, in the arrangement of lines shown in Figure 17.3.

The example also shows that there may be some infinite edges. To handle infinite edges like halflines and lines, we need a special vertex vinf at infinity. One can imagine that the PSLG is placed in a small almost flat disk D at the north pole of a giant sphere S and vinf is placed at the south pole. If an edge e is a halfline originating from a vertex u, then the endpoints of e are u and vinf .

One can view e as a curve on S from u near the north pole to vinf at the south pole, but e behaves as a halfline inside the disk D. If an edge e is a line, then vinf is the only endpoint of e. One can view e as a loop from vinf to the north pole and back, but e behaves as a line inside the disk D.

We do not allow isolated vertices, except for vinf . Planarity implies that the incident edges of each vertex are circularly ordered around that vertex. This applies to vinf as well. A PSLG data structure keeps three kinds of attributes: vertex attributes, edge attributes, and face attributes. The attributes of a vertex include its coordinates except for vinf (we assume that vinf is tagged to distinguish it from other vertices). The attributes of an edge include the equation of the support line of the edge (in the form of Ax + By + C = 0). The face attributes are useful for auxiliary information, e.g., color.