This paper proposes a novel method for global registration based on matching 3D medial structures of unorganized point clouds or triangulated meshes. Most practical known methods are based on the Iterative Closest Point (ICP) algorithm, which requires an initial alignment close to the globally optimal solution to ensure convergence to a valid solution. Furthermore, it can also fail when there are points in one dataset with no corresponding matches in the other dataset. The proposed method automatically finds an initial alignment close to the global optimal by using the medial structure of the datasets. For this purpose, we first compute the medial scaffold of a 3D dataset: a 3D graph made of special shock curves linking special shock nodes. This medial scaffold is then regularized exploiting the known transitions of the 3D medial axis under deformation or perturbation of the input data. The resulting simplified medial scaffolds are then registered using a modified graduated assignment graph matching algorithm. The proposed method shows robustness to noise, shape deformations, and varying surface sampling densities.