The conventional pattern-recognition star-identification algorithm requires parameter setting in advance and is slow under high limit magnitudes. A star-identification algorithm based on the Voronoi graph is proposed. The algorithm extracts stars in the star map and normalizes them to a spherical point set. Next, it calculates the Voronoi graph and the corresponding star polygon features, including the perimeter, area and number of edges to be combined into the star-recognition feature. Subsequently, the features are matched against the navigation catalog and pointing is calculated based on matching star pairs. Simulation results show that the algorithm is feasible and can yield the match ratio under different conditions. The operating time of the algorithm is less than 100 ms in the optimal case, and the effects of position noise, pseudo stars, and missing stars on the matching rate of the algorithm were tested and verified. The recognition rate of the proposed algorithm under different fields of view and limit magnitude was obtained experimentally, and the optimal combinations were obtained. The recognition rate of the algorithm does not decline under a 1‰ position error. A comparison with the star-identification algorithm using radial and cyclic features shows that the proposed algorithm offers a higher recognition rate, a shorter recognition time, and better anti-position noise performance than the conventional pattern-recognition star-map recognition algorithm. Furthermore, the proposed algorithm requires neither parameter setting nor adjustment.