Metric Graphs Elastically Embeddable In The Plane

    Authors

    J. Nievergelt;N. Deo

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Inf. Process. Lett.

    Keywords

    GRAPH EMBEDDING; LAYOUT; GRAPH DRAWING; RIGIDITY; FRAMEWORKS; DISTANCE; GEOMETRY; COMBINATORIAL PROBLEMS; COMPUTATIONAL GEOMETRY; RIGIDITY; Computer Science, Information Systems

    Abstract

    We study weighted graphs that can be embedded in the plane in such a way as to preserve an edge's weight as Euclidean distance between its two endpoints. Such questions arise in a variety of layout problems. In automatic graph drawing, for example, vertices are to be placed so as to approximate desired pairwise distances. The analogous 3-d problem arises in the distance geometry approach to molecular modeling, where edge weights are approximate distance measurements. We introduce the concept of elastic embeddability designed to deal with distances subject to error. Elastic graphs are related to, but distinct from, generically rigid graphs known in structural engineering. As an example that can be proven from basic graph-theoretic concepts, we characterize a subclass of elastic graphs: A chordal biconnected graph is elastically embeddable in the plane iff it does not contain the complete graph K4 as a subgraph.

    Journal Title

    Information Processing Letters

    Volume

    55

    Issue/Number

    6

    Publication Date

    1-1-1995

    Document Type

    Article

    Language

    English

    First Page

    309

    Last Page

    315

    WOS Identifier

    WOS:A1995RW02600003

    ISSN

    0020-0190

    Share

    COinS