Logo

Login

Planar Embeddings of Graphs with Specified Edge Lengths

Cabello, Sergio and Demaine, Erik D. and Rote, Günter (2004) Planar Embeddings of Graphs with Specified Edge Lengths. [Conference Paper]

Full text not available from this repository.

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.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.070 Area / Edge Length
ID Code:458
Deposited By:Selbach, Anna
Deposited On:09 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2912&spage=283

Repository Staff Only: item control page

References

B. Berger, J. Kleinberg, and T. Leighton. Reconstructing a three-dimensional model with arbitrary errors. In Proc. 28th Annu. ACM Sympos. Theory Comput., pages 449-458, May 1996.

C. Burnikel, R. Fleischner, K. Mehlhorn, and S. Schirra. A strong and easily computable separation bound for arithmetic expressions involving radicals. Algorithmica, 27(1):87-99, 2000.

C. Burnikel, S. Funke, K. Mehlhorn, S. Scirra, and S. Schmitt. A separation bound for real algebraic expressions. In Algorithms - ESA 2001, 9th Annual European Symposium, Proceedings, volume 2161 of Lecture Notes in Computer Science, pages 254-265. Springer-Verlag, 2001.

J. Campbell. Map Use and Analysis. McGraw-Hill, Boston, 4th edition, 2001.

S. Capkun, M. Hamdi, and J. Hubaux. GPS-free positioning in mobile ad-hoc networks. In Proceedings of the 34th Hawaii International Conference on System Science, pages 3481-3490, January 2001.

B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6(5):485-524, 1991.

R. Conelly. On generic global rigidity. In P. Gritzman and B. Sturmfels, editors, Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 147-155. AMS Press, 1991.

C. Coullard and A. Lubiw. Distance visibility graphs. Internat. J. Comput. Geom. Appl., 2(4):349-362, 1992.

G. M. Crippen and T. F. Havel. Distance Geometry and Molecular Conformation. John Wiley & Sons, 1988.

O. Devillers, G. Liotta, F. P. Preparata, and R. Tamassia. Checking the convexity of polytopes and the planarity of subdivisions. Comput. Geom. Theory Appl., 11:187-208, 1998.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

R. Diestel. Graph Theory. Springer-Verlag, New York, 2nd edition, 2000.

P. Eades and N. Wormald. Fixed edge length graph drawing is NP-hard. Discrete Appl. Math., 28:111-134, 1990.

H. Everett, C. T. Hoàng, K. Kilakos, and M. Noy. Distance segment visibility graphs. Manuscript, 1999. http://www.loria.fr/~everett/publications/distance.html.

J. Graver, B. Servatius, and H. Servatius. Combinatorial Rigidity. American Mathematical Society, 1993.

B. Hendrickson. Conditions for unique graph realizations. SIAM J. Comput., 21(1):65-84, February 1992.

B. Hendrickson. The molecule problem: Exploiting structure in global optimization. SIAM J. on Optimization, 5:835-857, 1995.

B. Jackson and T. Jordán. Connected rigidity matroids and unique realizations of graphs. Manuscript, March 2003.

D. E. Knuth and A. Raghunathan. The problem of compatible representatives. SIAM J. on Discrete Mathematics, 5(3):422-427, Aug. 1992.

C. Li and C. Yap. A new constructive root bound for algebraic expressions. In Proc. 12th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 496-505, 2001.

D. Lichtenstein. Planar formulae and their uses. SIAM J. Comput, 11(2):329-343, 1982.

J. Pach and P. Agarwal. Combinatorial Geometry. John Wiley & Sons, New York, NY, 1995.

F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 3rd edition, Oct. 1990.

N. B. Priyantha, A. Chakraborty, and H. Balakrishnan. The Cricket locationsupport system. In Proceedings of 6th Annual International Conference on Mobile Computing and Networking, pages 32-43, Boston, MA, August 2000.

C. Savarese, J. Rabaey, and J. Beutel. Locationing in distributed ad-hoc wireless sensor networks. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing, pages 2037-2040, Salt Lake City, UT, May 2001.

J. B. Saxe. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proc. 17th Allerton Conf. Commun. Control Comput., pages 480-489, 1979.

Y. Yemini. Some theoretical aspects of position-location problems. In Proc. 20th Annu. IEEE Sympos. Found. Comput. Sci., pages 1-8, 1979.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.