Automatic segmentation of the left atrium (LA) with the left atrial appendage (LAA) and the pulmonary vein (PV) trunks is important for intra-operative guidance in radio-frequency catheter ablation to treat atrial fibrillation (AF). Recently, we proposed a model-based method<sup>1, 2</sup> for LA segmentation from the C-arm CT images using marginal space learning (MSL).<sup>3</sup> However, on some data, the mesh from the model-based segmentation cannot exactly fit the true boundary of the left atrium in the image since the method does not make full use of local voxel-wise intensity information. Furthermore, due to the large variations of the PV drainage pattern, extra right middle pulmonary veins are not included in the LA model. In this paper, a graph-based method is proposed by exploiting the graph cuts method to refine results from the model-based segmentation and extract right middle pulmonary veins. We first build regions of interest to constrain the segmentation. The region growing method is used to construct graphs within the regions of interest for the graph cuts optimization. The graph cuts optimization is then performed and newly segmented foreground voxels are assigned into different parts of the left atrium. For the extraction of right middle pulmonary veins, occasional false positive PVs are removed by examining multiple criteria. Experiments demonstrate that the proposed graph-based method is effective and efficient to improve the LA segmentation accuracy and extract right middle PVs.