Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Sixteenth International Symposium on Graph Drawing, GD 2008
DOI: 10.7155/jgaa.00197
An Algorithm to Construct Greedy Drawings of Triangulations
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.
Submitted: November 2008.
Reviewed: October 2009.
Accepted: October 2009.
Final: November 2009.
Published: January 2010.
Communicated by Maurizio Patrignani and Ioannis G. Tollis
article (PDF)
BibTeX