This paper presents a novel graph theory based approach for restoring large scale power systems affected by complete blackouts. The proposed graph theory based method assesses the power system in blackout and represents the required information in a graph. The graph is initially used to determine the sectionalizing strategy. To do so, an un-normalized spectral clustering algorithm is implemented. The method then applies parallel power system restoration, restoring the created islands in parallel. Thus, the restoration process is speeded up. An algorithm for computing the k-shortest simple paths from the blackstart unit in each island to the non-blackstart units and loads in the same island is then carried out. By implementing the proposed method, cranking power can be rapidly sent to non-blackstart units and loads can be picked up quickly. The new graph theory based method is tested on the New England 39-bus test system. Simulation results are used to demonstrate the effectiveness of the proposed method on restoring systems affected by complete blackouts.