On Finding the Rectangular Duals of Planar Triangular Graphs
Xin He · SIAM Journal on Computing · 1993
This paper presents a new linear-time algorithm for finding rectangular duals of planar triangular graphs. The algorithm is conceptually simpler than the previously known algorithm. The coordinates of the rectangular dual constructed by the new algorithm are integers and carry clear combinatorial meaning.