Accession Number : ADA181390

Title :   Reduction of Flow Diagrams to Unfolded Form Modulo Snarls.

Descriptive Note : Final rept. 15 Sep 86-14 Feb 87,

Corporate Author : YLYK LTD ANN ARBOR MI

Personal Author(s) : Blakley,George R , III

PDF Url : ADA181390

Report Date : 14 Apr 1987

Pagination or Media Count : 91

Abstract : This research effort produced five low-degree polynomial time algorithms for turning a complete but merely local description of a flow diagram (or graph). The most remarkable feature of these five algorithms is that all of them overcome the problem of scale. This means that the representations they produce have the property that the operation boxes on flow paths (or vertices and edges) are drawn with a uniform spacing which exhibits neither crowding nor excessive white space. Every output of every one of them is very readable. The most important of them produces a plane, straight-line drawing, without crossovers, of any planar graph. The drawing can be performed in a natural and uncrowded manner on a 3v by 2v piece of graph paper, where v is the number of vertices in the graph. The research relates these graph-representation problems to fundamental problems in structured programming, especially the role of GOTOs and the uses of new non-imperative paradigms.

Descriptors :   *ALGORITHMS, *GRAPHS, FLOW FIELDS, COMPUTER PROGRAMMING, FLOW CHARTING, SCALE, ENGINEERING DRAWINGS, POLYNOMIALS, DIAGRAMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE