Title

Metric Graphs Elastically Embeddable In The Plane

Keywords

Combinatorial problems; Computational geometry; Distance geometry; Frameworks; Graph drawing; Graph embedding; Layout; Rigidity

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. © 1995.

Publication Date

9-29-1995

Publication Title

Information Processing Letters

Volume

55

Issue

6

Number of Pages

309-315

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0020-0190(95)00103-J

Socpus ID

0043083385 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0043083385

This document is currently not available here.

Share

COinS