Accession Number:

AD0648133

Title:

PLANAR REPRESENTATIONS OF COMPLEX GRAPHS

Descriptive Note:

Technical note

Corporate Author:

MASSACHUSETTS INST OF TECH LEXINGTON LINCOLN LAB

Personal Author(s):

Report Date:

1967-02-06

Pagination or Media Count:

44.0

Abstract:

The papers major topic is the problem of constructing good two- dimensional representations, using straight lines as edges, of complex, generally non-planar graphs. Two precise measures that correlate well with the subjective clarity of planar representations of randomly generated graphs are proposed. One is the number of edge intersections that do not correspond to graph vertices. The second measure, called infidelity, quantifies the degree to which the distance between pairs of vertices in a particular metric in the plane corresponds to their graph-theoretical distance from one another. Some experiments in graph representation, using the TX-2 computer on-line display, are described. Heavy emphasis is given the definition of the infidelity measure, the nature of its correlation with graph clarity, and some theorems which add to its characterization. Included is a discussion of heuristics for the simplification of a graph representation. In conclusion, there is presented a sketch of a model of a graph theory computer package that should be useful to a researcher or student of graph theory.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE