Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00197 An Algorithm to Construct Greedy Drawings of Triangulations Patrizio Angelini , Fabrizio Frati , and Luca Grilli Vol. 14, no. 1, pp. 19-51, 2010. Regular paper Abstract We show an algorithm to construct a greedy drawing of every given triangulation. The algorithm relies on two main results. First, we show how to construct greedy drawings of a fairly simple class of graphs, called triangulated binary cactuses. Second, we show that every triangulation can be spanned by a triangulated binary cactus. Further, we discuss how to extend our techniques in order to prove that every triconnected planar graph admits a greedy drawing. Such a result, which proves a conjecture by Papadimitriou and Ratajczak, was independently shown by Leighton and Moitra.
|
Accepted: October 2009. Published: January 2010. Reviewed: October 2009. Final: November 2009. Submitted: November 2008. Communicated by Maurizio Patrignani and Ioannis Tollis |
Journal of Graph Algorithms and Applications |