Linear programming is commonly used in earthwork hauling plan. However special expertise in forming and solving linear equations, along with considerable efforts in interpreting results, is required to apply these methods in practice. Moreover, previous methods mainly focus on cost estimation and thus largely ignore the constructability issues; this makes earthwork hauling plan impractical for construction planning. We aim to address these problems by introducing an intuitive graph based approach which optimizes the earthwork hauling plan using the minimum cost flow network. We choose the total traveling time as the objective function to be minimized in order to separate the earthwork hauling plan from other factors such as fleet combination. Our method directly connects adjacent sections allowing accessibility between them, instead of connecting the centers of cut and fill cells as potential haul routes as in previous methods. As a result, the proposed method is capable to handle constructability issues caused by “soft blocks”-which cannot be eliminated in establishing the standard flow network as their existence impose constraints on the grading plan. The graphic earth flow network can be used to guide the execution of the earthwork project and generate multiple grading plans, providing more flexibility compared to traditional methods. We present an earthmoving example with a reserved soft area and show that the proposed method is graphically intuitive, easy to establish and able to handle soft blocks.