Title

Metric Graphs Elastically Embeddable In The Plane

Authors

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