Spatial maps are abstract representations of the environment for navigation purposes. Many of these maps are too detailed and too large to be useful for small, low cost mobile robots, viz., tetherless, autonomous robots each occupying a volume of about a cubic foot or less. This paper explores cheaper alternatives of spatial maps. The key components of spatial maps are the locally detectable features, the spatial relationships between the features, the groupings of these features for forming a local region, and networks of local regions to form larger regions. Regions, local or otherwise, are graphs with nodes representing local regions and arcs representing the spatial relationship between the regions. To achieve a compact representation, restrictions are placed on the number of kinds of locally detectable features, the possible kinds of spatial relationship, and the total number nodes possible in a graph. A compact spatial map for small mobile robots navigating in a hallway environment is discussed. A small number of features are needed to represent local neighborhoods in such environments. This and other factors make it possible to use compact spatial maps to represent such environments. Extending such maps to handle more general cases is possible in many situations.