This paper proposes a sectionalizing planning for parallel power system restoration after a complete system blackout. Parallel restoration is conducted in order to reduce the total restoration process time. Physical and operation knowledge of the system, operating personnel experience, and computer simulation are combined in this planning to improve the system restoration and serve as a guidance for system operators/planners. Sectionalizing planning is obtained using discrete evolutionary programming optimization method assisted by heuristic initialization and graph theory approach. Set of transmission lines that should not be restored during parallel restoration process (cut set) is determined in order to sectionalize the systeminto subsystems orislands. Each island with almost similar restoration time is set as an objective function so as to speed up the resynchronization of the islands. Restoration operation and constraints (black start generator availability, load-generation balance and maintaining acceptable voltage magnitude within each island) is also taken into account in the course of this planning. The method is validated using the IEEE 39-bus and 118-bus system. Promising results in terms of restoration time was comparedto other methods reported in the literature.