Methods for the graph realization problem

Abstract

The graph realization problem seeks an answer to how and under what conditions a graph can be constructed if we know the degrees of its vertices. The problem was widely studied by many authors and in many ways, but there are still new ideas and solutions. In this sense, the paper presents the known necessary and su cient conditions for realization with the description in pseudocode of the corresponding algorithms. Two cases to solve the realization problem are treated: finding one solution, and finding all solutions. In this latter case a parallel approach is presented too, and how to exclude isomorphic graphs from solutions. We are also discussing algorithms using binary integer programming and flow networks.

Keywords

• degree sequences
• graph realization algorithms
• flow networks
• graphical lists
• bigraphical lists
• modified edmonds–karp algorithm