Data structures for topological and geometric operations on networks

The growing interest in computer graphics and Geographical Information Systems has made it necessary to develop efficient data structures and algorithmic procedures for handling graphical information in real-time. In this paper, we consider the problem of storage and manipulation of large-scale networks which can undergo dynamic changes. Two complementary data structures are presented: a topological and a topographical representation. The objective is to support both graph-theoretic and geometric operations efficiently. A topological representation facilitates the implementation of graph-theoretic optimization algorithms such as the shortest path and spanning tree problems. In this context, a new dynamic forward star structure is developed and contrasted with the classic (static) forward star representation of sparse graphs. Algorithmic procedures and complexity analysis for network editing operations of this structure are provided. A topographical representation is necessary for geometric operations such as nearest neighbour location and range retrieval. Algorithms for performing editing and geometric operations on the BD-tree are presented. Finally, the practical efficiency of the data structures is investigated by computational experiments on large-scale road networks.