Tracing of vessels is one of the most fundamental techniques in a computer-aided diagnostic (CAD) scheme for vascular systems. A major challenge of methods for tracing vessels is to trace vessels robustly against noise, vessel branching, vessel size changes, and curved vessels, because those factors often lead to errors in tracing. Among them, the robustness against vessel size changes is especially important for a CAD scheme for estimating stenosis. Our purpose in this study was to develop a robust algorithm for tracing vessels on coronary angiograms. Our algorithm for tracing vessels consists of (1) a radial search for candidates based on the gray level information, (2) expansion of candidate paths based on a tree graph, and (3) determination of the path based on the gray level information and a smoothness constraint on the path. To evaluate the performance of our tracing algorithm, we applied it to digital subtraction angiograms of coronary arteries with stenoses. In these experiments, we showed that our tracing algorithm was robust against noise, vessel branching, vessel size changes, and curved vessels. Thus, our algorithm would be useful for a CAD scheme for vascular systems.