A very recently developed optimization algorithm for carbon clusters (Cns) (Yen and Lai J Chem Phys 142:084313, 2015) is combined separately with different empirical bond-order potentials which were proposed also for carbon materials, and they are applied to calculate the lowest energy structures of Cns studying their structural changes at different size n. Based on predicted structures, we evaluate the practicality of four analytic bond-order empirical potentials, namely the Tersoff, Tersoff–Erhart–Albe, first-generation Brenner and second-generation Brenner (SGB) potentials. Generally, we found that the cluster Cn (n = 3–60) obtained by the SGB potential undergoes a series of dramatic structural transitions, i.e., from a linear → a single ring → a multi-ring/quasi-two-dimensional bowl-like → three-dimensional fullerene-like shape; such variability of structural forms was not seen in the other three potentials. On closer examination of the Cns calculated using this potential and further comparing them with those obtained by the semiempirical density functional tight-binding theory calculations, we found that these Cn are more realistic than similar works reported in the literature. In this respect, due to its potential applications in the study of chemically complex systems of different atoms especially chemical reactions (Che et al. Theor Chem Acc 102:346, 1999), the SGB potential can, moreover, be used to investigate larger size Cn, and calculated structural results by this potential are naturally input configurations for higher-level density functional theory calculations. Another most remarkable finding in the present work is the Cn results calculated by Tersoff–Erhart–Albe empirical potential. It predicts a two-dimensional development of graphene structure, exhibiting always a zigzag edge in the optimized clusters. This empirical potential can thus be applied to study graphene-related materials such as that shown in a recent paper (Yoon et al. J Chem Phys 139:204702, 2013).