An Algorithm to Construct Greedy Drawings of Triangulations

Angelini, Patrizio and Frati, Fabrizio and Grilli, Luca (2008) An Algorithm to Construct Greedy Drawings of Triangulations. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 26-37 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_4).

Full text not available from this repository.

Abstract

We show an algorithm to construct greedy drawings of every given triangulation.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_4
Classifications:G Algorithms and Complexity > G.490 Embeddings
ID Code:886

Repository Staff Only: item control page

References

Ben-Chen, M., Gotsman, C., Gortler, S.J.: Routing with guaranteed delivery on virtual coordinates. In: CCCG 2006 (2006)

Ben-Chen, M., Gotsman, C., Wormser, C.: Distributed computation of virtual coordinates. In: Erickson, J. (ed.) SoCG 2007. pp. 210–219. ACM (2007)

Dhandapani, R.: Greedy drawings of triangulations. In: Huang, S.T. (ed.) SODA 2008. pp. 102–111. SIAM (2008)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Kleinberg, R.: Geographic routing using hyperbolic space. In: INFOCOM ’07. pp. 1902– 1909. IEEE (2007)

Knaster, B., Kuratowski, C., Mazurkiewicz, C.: Ein beweis des fixpunktsatzes fur n dimensionale simplexe. Fundamenta Mathematicae 14, 132–137 (1929)

Leighton, T., Moitra, A.: Some results on greedy embeddings in metric spaces. In: FOCS 2008 (2008)

Papadimitriou, C.H., Ratajczak, D.: On a conjecture related to geometric routing. Theor. Comput. Sci. 344(1), 3–14(2005)

Rao, A., Papadimitriou, C.H., Shenker, S., Stoica, I.: Geographic routing without location information. In: Johnson, D.B., Joseph, A.D., Vaidya, N.H. (eds.) MOBICOM 2003. pp. 96–108. ACM Press, New York (2003)

Schnyder, W.: Embedding planar graphs on the grid.In: SODA 1990. pp. 138–148. SIAM, Philadelphia (1990)