Topology-based maps are a new representation of the workspace of a mobile robot based on the topological notions of connectivity and adjacency. In this paper, we show how to enrich a topology-based map with geometric information useful for planning and navigation. Both the topology-based map and this geometric information are automatically extracted from sensor data.