Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00145
Planar Embeddings of Graphs with Specified Edge Lengths
Vol. 11, no. 1, pp. 259-276, 2007. Regular paper.
Abstract We consider the problem of finding a planar straight-line embedding of a graph
with a prescribed Euclidean length on every edge. There has been substantial
previous work on the problem without the planarity restrictions, which has
close connections to rigidity theory, and where it is easy to see that the
problem is NP-hard. In contrast, we show that the problem is
tractable-indeed, solvable in linear time on a real RAM-for
straight-line embeddings of planar 3-connected triangulations, even if the outer face is
not a triangle. This result is essentially tight: the problem becomes NP-hard
if we consider instead straight-line embeddings of planar 3-connected infinitesimally
rigid graphs with unit edge lengths,
a natural relaxation of triangulations in this context.
|
Journal Supporters
|