Paper by Erik D. Demaine
- Sergio Cabello, Erik D. Demaine, and Günter Rote, “Planar Embeddings of Graphs with Specified Edge Lengths”, Journal of Graph Algorithms and Applications, volume 11, number 1, 2007, pages 259–276.
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.
- This paper is also available from the journal.
- The paper is 18 pages.
- The paper is available in gzipped PostScript (3335k) and PDF (2670k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- PlanarEmbedding_GD2003 (Planar Embeddings of Graphs with Specified Edge Lengths)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 13, 2019 by