We present a method to track vessels in angiography [contrast filled vessels in two-dimensional (2-D) x-ray fluoroscopy]. Finding correspondence of a vessel tree from consecutive angiogram frames provides significant value in computer-aided clinical applications such as fast vessel tree segmentation, three-dimensional (3-D) vessel topology reconstruction from corresponding centerlines, cardiac motion understanding, etc. However, establishing an accurate vessel tree correspondence (vessel tree tracking) is a nontrivial problem due to nonlinear periodic cardiac and breathing motion in 2-D views, foreshortening, false bifurcations due to 3-D to 2-D projection, occlusion from other anatomies, etc. The vessel tree is represented by BSpline curves. The control points of the BSpline curves are landmarks that are the tracking targets. Our method maximizes the appearance similarity while preserving the vessel structure. A directed acyclic graph (DAG) is employed to represent the appearance and shape structure of the vessel tree: nodes from the DAG encode the appearance of the vessel tree landmarks, and the edges encode the relative locations between landmarks. The vessel tree tracking problem turns into finding the most similar tree from the DAG in the next frame, and it is solved using an efficient dynamic programming algorithm. We performed evaluations on 62 x-ray angiography sequences (above 1000 frames). Experiment results show our algorithm is robust to these challenges and delivers better performance, compared to four existing methods.