This paper presents an alternative approach to building representations for the environment of a mobile robot. This approach is based on recording the geometrical relationships between the observed features rather than their absolute position with respect to an arbitrary coordinate frame of reference. The resulting representation takes the form of a graph where the nodes represent the observed features and the edges represent the relationships between the features. This representation is particularly well suited for recognition tasks which can be reformulated as graph matching problems. Unlike Cartesian maps, relational maps can be built and maintained without any estimates for the position of the robot which means that the errors in this representation will be independent of any errors in the estimates for the robot position.