We investigate the complexity and expressive power of the spatial logic for querying
graphs introduced by Cardelli, Gardner and Ghelli (ICALP 2002).We show that the model-checking
complexity of versions of this logic with and without recursion is PSPACE-complete. In terms of
expressive power, the version without recursion is a fragment of the monadic second-order logic
of graphs and we show that it can express complete problems at every level of the polynomial
hierarchy. We also show that it can define all regular languages, when interpretation is restricted to
strings. The expressive power of the logic with recursion is much greater as it can express properties
that are PSPACE-complete and therefore unlikely to be definable in second-order logic.