Reduction of Flow Diagrams to Unfolded Form Modulo Snarls.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 14, 1987
- Accession Number
- ADA181390
Entities
People
- George R. Blakley Iii