Setup planning is the act of preparing detailed work instructions for setting up a part. The purpose of setting up a part is to ensure its stability during machining and, more importantly, the precision of the machining processes. Therefore, tolerance control can be achieved proactively via setup planning. This fact was somewhat overlooked in the computer-aided process planning (CAPP) research community. While many researchers focused their attention on tolerance chart analysis, the issue of tolerance analysis for setup planning was relatively unexplored. To systematically solve the setup planning problem, a graph theoretical approach is proposed. The design specification of a part is represented as a graph. The problem of identifying the optimal setup plan is transformed into a graph search problem. A setup planning algorithm for rotational parts was then developed. The algorithm was evaluated and found to be both efficient and effective.