An Algorithm to Construct Greedy Drawings of Triangulations - Angelini, Patrizio; Frati, Fabrizio; Grilli, Luca (Journal of Graph Algorithms and Applications, 2010)
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. <!—->