Planar Straight Line Graphs:Operations on PSLGs

Operations on PSLGs

The operations on a PSLG can be classified into access functions and structural operations. The access functions retrieve information without modifying the PSLG. Since the access functions partly depend on the data structure, we discuss them later when we introduce the data structures. In this section, we discuss four structural operations on PSLGs: edge insertion, edge deletion, vertex split, and edge contraction. We concentrate on the semantics of these four operations and discuss the implementation details later when we introduce the data structures. For vertex split and edge contraction, we assume further that each face in the PSLG is a simple polygon as these two operations are usually used under such circumstances.

Edge insertion and deletion

When a new edge e with endpoints u and v is inserted, we assume that e does not cross any existing edge. If u or v is not an existing vertex, the vertex will be created. If both u and v are new vertices, e is an isolated edge inside a face f . Since each face is assumed to have exactly one boundary, this case happens only when the PSLG is empty and f is the entire plane. Note that e becomes a new boundary of f . If either u or v is a new vertex, then the boundary of exactly one face gains the edge e. If both u and v already exist, then u and v lie on the boundary of a face which is split into two new faces by the insertion of e. These cases are illustrated in Figure 17.4.

The deletion of an edge e has the opposite effects. After the deletion of e, if any of its endpoint becomes an isolated vertex, it will be removed. The vertex vinf is an exception and it is the only possible isolated vertex. The edge insertion is clearly needed to create

a PSLG from scratch. Other effects can be achieved by combining edge insertions and deletions appropriately. For example, one can use the two operations to overlay two PSLGs in a plane sweep algorithm, see Figure 17.5.

Vertex split and edge contraction

The splitting of a vertex v is best visualized as the continuous morphing of v into an edge e. Depending on the specification of the splitting, an incident face of v gains e on its boundary or an incident edge of v is split into a triangular face, see Figure 17.6.

The incident edges of v are displaced and it is assumed that no self-intersection occurs within the PSLG during the splitting. The contraction of an edge e is the inverse of the vertex split. We also assume that no self-intersection occurs during the edge contraction. If e is incident on a triangular face, that face will disappear after the contraction of e.

Not every edge can be contracted. Consider an edge ab. If the PSLG contains a cycle abv that is not the boundary of any face incident to ab, we call the edge ab non-contractible because its contraction is not cleanly defined. Figure 17.7 shows an example. In the figure, after the contraction, there is an ambiguity whether dv should be incident on the face f1 or the face f2. In fact, one would expect the edge dv to behave like av and bv and be incident on both f1 and f2 after the contraction. However, this is impossible.

The vertex split and edge contraction have been used in clustering and hierarchical draw- ing of maximal planar graphs [6].