GeoGraph: A Topological Storage Model for Extensible GIS

Topological data structures are useful for reducing the cost of geometrical operations within a Geographic Information System (GIS). Unfortunately, manipulating such data structures can be quite complex — especially when supporting multiple, overlapping geographical maps. The GeoGraph storage model proposed in this paper solves this problem. It is implemented as a toolbox, and is used as a low-level system layer for support of a GIS. The Ge"oGraph storage model is based on a graph with the corresponding basic traversal primitives, and can be integrated within an extensible relational DBMS so that important spatial operations can be directly executed by graph traversals. Furthermore, the graph is decomposable so that only the useful subset of the database can be loaded from disk without format conversion. 1