Paper by Erik D. Demaine
- Sergio Cabello, Erik D. Demaine, and Günter Rote, “Planar Embeddings of Graphs with Specified Edge Lengths”, in Proceedings of the 11th Symposium on Graph Drawing (GD 2003), Lecture Notes in Computer Science, volume 2912, Perugia, Italy, September 21–24, 2003, pages 283–294.
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.
- The paper is \copyright Springer-Verlag.
- The paper is 12 pages.
- The paper is available in PostScript (6771k), gzipped PostScript (644k), and PDF (2997k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- PlanarEmbedding_JGAA (Planar Embeddings of Graphs with Specified Edge Lengths)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 1, 2023 by