## Transversal structures on triangulations, with application to straight-line drawing
Fusy, Éric
(2006)
Full text not available from this repository. ## AbstractWe define and study a structure called transversal edge-partition 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 straight-line drawing algorithm for triangulations without non empty triangles, and more generally for 4-connected 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( 1-frac{5}{27} ight) imes frac{n}{2}cdotleft( 1-frac{5}{27} ight) up to fluctuations of order sqrt{n}, and the half-perimeter is bounded by n-1. The best previously known algorithms for straight-line drawing of such triangulations only guaranteed a grid of size (lceil n/2 ceil -1) imes lfloor n/2 floor. The reduction-factor of frac{5}{27} can be explained thanks to a new bijection between ternary trees and triangulations of the 4-gon without non empty triangles.
Repository Staff Only: item control page References |