Reconstruction graphs and testing their properties in a relational spatial database

Among other representations, the relational databases are also widely used for storing spatial data. The model presented in this paper is a slightly modified version of the PLA database [1]. This spatial relational model serves to represent the topological properties of geographic data. In this paper, we first investigate the conditions for recognizing some types of the represented graph. We show how connectivity, 2-connectivity, Eulerian graphs, etc., can be characterized using just one relation of the database. Second, we point out redundancies in the representation and connections among the four relations of the database. Moreover, we design efficient (linear-time) algorithms for data retrieval/reconstruction of the stored spatial object, both in the planar and spherical cases. They also serve as constraints checking.