Transversal structures on triangulations, with application to straight-line drawing

Fusy, Éric (2006) Transversal structures on triangulations, with application to straight-line drawing. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 177-188(Official URL: http://dx.doi.org/10.1007/11618058_17).

Full text not available from this repository.

Abstract

We 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.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_17
Classifications: P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.630 Labeling
URI: http://gdea.informatik.uni-koeln.de/id/eprint/690

Actions (login required)

View Item View Item