O'Reilly logo

Handbook of Data Structures and Applications, 2nd Edition by Sartaj Sahni, Dinesh P. Mehta

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

18

Planar Straight Line Graphs*

Siu-Wing Cheng

Hong Kong University of Science and Technology

18.1Introduction

18.2Features of PSLGs

18.3Operations on PSLGs

Edge Insertion and DeletionVertex Split and Edge Contraction

18.4Winged-Edge

18.5Halfedge

Access FunctionsEdge Insertion and DeletionVertex Split and Edge Contraction

18.6Quadedge

18.7Further Remarks

18.8Glossary

Acknowledgments

References

18.1Introduction

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 [1] in which each vertex keeps a list of vertices connected to it by edges. In a typical ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required