Planar Embeddings of Graphs with Specified Edge Lengths

Authors

  • Sergio Cabello
  • Erik Demaine
  • Günter Rote

DOI:

https://doi.org/10.7155/jgaa.00145

Keywords:

embedding , unit length , rigidity , straight-line drawing , NP-hardness

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.

Downloads

Download data is not yet available.

Downloads

Published

2007-01-01

How to Cite

Cabello, S., Demaine, E., & Rote, G. (2007). Planar Embeddings of Graphs with Specified Edge Lengths. Journal of Graph Algorithms and Applications, 11(1), 259–276. https://doi.org/10.7155/jgaa.00145

Issue

Section

Articles

Categories