Multiplanar extension of nonplanar directed graphs

Abstract

An analysis of planar and nonplanar aspects of program flow is presented. Basic blocks of computer programs are treated as vertices in a directed graph. Nonplanar programs are embedded in multiple planes. Elements of graph theory are given in order to provide the necessary background for the use of graph terminology. Numerous examples of applications of graph theory are presented. A search method known as the Depth First Search (DFS) is a primary technique utilized in many phases of the presented system. It is used to divide an arbitrary directed graph into biconnected components which are separately analyzed for planarity. The initial directed graph is obtained from parsing FORTRAN source code. Biconnected components which are determined to be nonplanar using a "two stack" algorithm are then analyzed to determine a multiplanar embedding. A series of 22 FORTRAN programs are examined for planarity and a table is given summarizing the results of this investigation. Attempts at correlation of various ratios to nonplanar programs are also discussed. Two optimization phases are undertaken in an attempt to minimize the number of crossings in the initial embedded plane and the number of extended planes required for embedding of nonplanar configurations. Specific paths that cross each other are identified by path number. Sufficient information is given for actual multiplanar embedding.