Biometrics such as retina, palm vein, wrist vein and hand vein are becoming increasingly popular because of ease of use, in-built liveness detection and a contact free capture process. Here the authors show the benefits of graph representation for all such vascular biometrics and the advantages of graph topology in matching vascular biometric graphs. The authors find that different types of small substructures dominate in the four classes of vascular graphs due to the way the vasculature is built in the human body. The authors show that simple graph structures can be used to bring down the registration time by over 50% compared with registration using edges alone, and that cost functions that include matching the local graph neighbourhood around compared node pairs improve matching performance. Distance measures based on the number of vertices or edges in the maximum common subgraph are shown to discriminate significantly better than using a simple count of matched vertices, as in the iterative closest point based point pattern matching. For graphs whose topology is close to that of proximity graphs, edgebased distance measures were found to perform best. These results are demonstrated for all four vascular modalities.