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, Limerick, Ireland , pp. 177-188 (Official URL:

Full text not available from this repository.


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
ID Code:690

Repository Staff Only: item control page


Therese C. Biedl, Goos Kant, and Michael Kaufmann.: On triangulating planar graphs under the four-connectivity constraint. Algorithmica, 19(4):427-446, 1997.

N. Bonichon, S. Felsner, and M. Mosbah.: Convex drawings of 3-connected plane graphs. GD '04: Proceedings of the Symposium on Graph Drawing, pages 287-299. Springer-Verlag, 2004.

N. Bonichon, C. Gavoille, N. Hanusse, D. Poulalhon, and G. Schaeffer.Planar graphs, via well-orderly maps and trees. 30^{th} International Workshop, Graph - Theoretic Conceptsin Computer Science (WG), volume 3353 of Lecture Notes in Computer Science, pages 270-284. Springer-Verlag, 2004.

H. de Fraysseix, P. Ossona de Mendez, and J. Pach.: Representation of planar graphs by segments. Intuitive Geometry, 63:109-117, 1991.

H. de Fraysseix, P. Ossona de Mendez, and P. Rosenstiehl.: Bipolar orientations revisited. Discrete Appl. Math., 56(2-3):157-179, 1995.

P. O. de Mendez.: Orientations bipolaires. PhD thesis, Paris, 1994.

Stefan Felsner.: Lattice structures from planar graphs. Electronic Journal of Combinatorics, (R15):24p., 2004.

E. Fusy, D. Poulalhon, and G. Schaeffer.: Dissections and trees, with applications to optimal mesh encoding and to random sampling. 16th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2005.

X. He.: Grid embedding of 4-connected plane graphs. GD '95: Proceedings of the Symposium on Graph Drawing, pages 287-299. Springer-Verlag, 1996.

G. Kant and Xin He.:Regular edge labeling of 4-connected plane graphs and its applications in graph drawing problems. Theoretical Computer Science, 172(1-2):175-193, 1997.

K. Miura, S. Nakano, and T. Nishizeki.:Grid drawings of four-connected plane graphs. Disc. Comput. Geometry, 26(2):73-87, 2001.

D. Poulalhon and G. Schaeffer.: Optimal coding and sampling of triangulations. Automata, Languages and Programming. 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings, volume 2719 of Lecture Notes in Computer Science, pages 1080-1094. Springer-Verlag, 2003.

G. Schaeffer.: Conjugaison d'arbres et cartes combinatoires aleatoires. PhD thesis, Université Bordeaux I, 1998.

G. Schaeffer.: Random sampling of large planar maps and convex polyhedra. Annual ACM Symposium on Theory of Computing (Atlanta, GA,1999), pages 760-769 (electronic). ACM, New York, 1999.

W. Schnyder.: Planar graphs and poset dimension. Order, 5:323-343, 1989.

W. Schnyder.: Embedding planar graphs on the grid. SODA '90: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pages 138-148, 1990.

W. T. Tutte.: A census of planar triangulation. Canad. J. Math. , 14:21-38, 1962.