Transversal structures on triangulations, with application to straightline drawingFusy, Éric (2006) Transversal structures on triangulations, with application to straightline drawing. In: Graph Drawing 13th International Symposium, GD 2005, September 1214, 2005 , pp. 177188(Official URL: http://dx.doi.org/10.1007/11618058_17). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/11618058_17
AbstractWe define and study a structure called transversal edgepartition related to triangulations without non empty triangles, which is equivalent to the regular edge labeling discovered by Kant and He. We study other properties of this structure and show that it gives rise to a new straightline drawing algorithm for triangulations without non empty triangles, and more generally for 4connected plane graphs with at least 4 border vertices. Taking uniformly at random such a triangulation with 4 border vertices and n vertices, the size of the grid is almost surely frac{n}{2}cdotleft( 1frac{5}{27} ight) imes frac{n}{2}cdotleft( 1frac{5}{27} ight) up to fluctuations of order sqrt{n}, and the halfperimeter is bounded by n1. The best previously known algorithms for straightline drawing of such triangulations only guaranteed a grid of size (lceil n/2 ceil 1) imes lfloor n/2 floor. The reductionfactor of frac{5}{27} can be explained thanks to a new bijection between ternary trees and triangulations of the 4gon without non empty triangles.
Actions (login required)
