This paper investigates a methodology and corresponding graph modeling of process planning for cylindrical machined parts with tolerancing. Methods and techniques for representing possible process plans, reducing the complexity and eliminating over-toleranced plans are developed. The method first maps each feature of a part into feasible finishing processes that are capable to achieve the specified tolerances associated with the feature. All possible process plans are then developed by expanding preceding processes of each finishing process. The expanded processes form a graph, or a forest, with processes as nodes and process sequence as links. Processes with same specifications can be further merged and pruned to reduce the complexity of the graph. Tolerance stack-up of each possible plan for simplified results is also further computed by tolerance chart such that over-toleranced plans are eliminated. As there are often many feasible plans for machining a part, the qualified plan that satisfies design specifications is achieved by traversal through the graph imposing tolerance chart. An example is also demonstrated to illustrate the approach and the model. The merit of this method is to employ a unified graph model for representing and reasoning.