We present a novel method for the localization of an autonomous vehicle in two dimensions. Instead of focussing on properties of obstacles, we emphasize the description of free-space. We introduce the concept of signature graphs which is a compact data structure describing available free-space of an environment. It therefore also represents a map of the environment. A signature is an edge in the graph and is defined by seven parameters. An edge indicates that it is possible for the vehicle to move between two graph nodes. The signature graph is flexible and can easily be updated as new information about the environment is collected. We have with an autonomous wheelchair implemented our methods and tests them with successful results