Sergio Cabello, Erik D. Demaine, and Günter Rote:
Planar embeddings of graphs with specified edge lengths
- In: "Graph Drawing". GD 2003, Proceedings of the 11th
International
Symposium on Graph Drawing, Perugia, September 2003, Revised Papers.
Editor:
Giuseppe Liotta. Lecture Notes in Computer Science, 2912,
Springer-Verlag, 2004,
pp. 283–294.
doi:10.1007/978-3-540-24595-7_26
- Journal of Graph Algorithms
and Applications
11, No. 1 (2007), pp. 259–276.
doi:10.7155/jgaa.00145
Abstract
We consider the problem of finding a planar embedding of a planar
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 planar 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 planar embeddings of planar 3-connected infinitesimally rigid
graphs, a
natural relaxation of triangulations in this context.
Last update: October 12, 2007.