Graphs provide a powerful representation formalism for handwritten signatures, capturing local properties as well as their relations. Yet, although introduced early for signature verification, only a few current systems rely on graph-based representations. A possible reason is the high computational complexity involved for matching two general graphs. In this paper, we introduce a novel structural approach to offline signature verification using an efficient cubic-time approximation of graph edit distance. We put forward several ways of creating, normalizing, and comparing signature graphs built from keypoints and investigate their performance on three benchmark datasets. The experiments demonstrate a promising performance of the proposed structural approach when compared with the state of the art.