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