Abstract
Schnyder woods are a well-known combinatorial structure for plane triangulations, which yields a decomposition into three spanning trees. We extend here definitions and algorithms for Schnyder woods to closed orientable surfaces of arbitrary genus. In particular, we describe a method to traverse a triangulation of genus g and compute a so-called g-Schnyder wood on the way. As an application, we give a procedure to encode a triangulation of genus g and n vertices in 4n+O(glog (n)) bits. This matches the worst-case encoding rate of Edgebreaker in positive genus. All the algorithms presented here have execution time O((n+g)g) and hence are linear when the genus is fixed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barbay, J., Castelli-Aleardi, L., He, M., Munro, J.I.: Succinct representation of labeled graphs. In: ISAAC, pp. 316–328 (2007)
Bernardi, O., Bonichon, N.: Intervals in Catalan lattices and realizers of triangulations. J. Comb. Theory, Ser. A 116(1), 55–75 (2009)
Bonichon, N.: Aspects algorithmiques et combinatoires des réaliseurs des graphes plans maximaux. PhD thesis, Bordeaux I (2002)
Bonichon, N., Gavoille, C., Hanusse, N.: An information-theoretic upper bound of planar graphs using triangulation. In: STACS, pp. 499–510. Springer, Berlin (2003)
Bonichon, N., Gavoille, C., Labourel, A.: Edge partition of toroidal graphs into forests in linear time. In: ICGT, vol. 22, pp. 421–425 (2005)
Bonichon, N., Gavoille, C., Hanusse, N., Poulalhon, D., Schaeffer, G.: Planar graphs, via well-orderly maps and trees. Graphs Comb. 22(2), 185–202 (2006)
Brehm, E.: 3-orientations and Schnyder-three tree decompositions. Master’s thesis, Freie Universität Berlin (2000)
Cabello, S., Mohar, B.: Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Discrete Comput. Geom. 37(2), 213–235 (2007)
Castelli-Aleardi, L., Devillers, O., Schaeffer, G.: Succinct representation of triangulations with a boundary. In: WADS, pp. 134–145. Springer, Berlin (2005)
Castelli-Aleardi, L., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci. 408, 174–187 (2008) (Preliminary version in SoCG’06)
Chapuy, G.: Asymptotic enumeration of constellations and related families of maps on orientable surfaces. arXiv:0805.0352 (2008)
Chapuy, G., Marcus, M., Schaeffer, G.: A bijection for rooted maps on orientable surfaces. arXiv:0712.3649 (2007)
Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications to graph encoding and graph drawing. In: SODA, pp. 506–515 (2001)
Chuang, R.C.-N., Garg, A., He, X., Kao, M.-Y., Lu, H.-I.: Compact encodings of planar graphs via canonical orderings and multiple parentheses. In: ICALP, pp. 118–129 (1998)
de Fraysseix, H., de Mendez, P.O.: On topological aspects of orientations. Discrete Math. 229, 57–72 (2001)
de Mendez, P.O.: Orientations bipolaires. PhD thesis, Paris (1994)
de Verdière, E.C., Lazarus, F.: Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33(3), 507–534 (2005). (Preliminary version in FOCS’02)
Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37–59 (2004)
Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order 18, 19–37 (2001)
Felsner, S.: Lattice structures from planar graphs. Electron. J. Comb. 11(15), 24 (2004)
Fusy, É.: Combinatoire des cartes planaires et applications algorithmiques. PhD thesis, Ecole Polytechnique (2007)
Fusy, É., Poulalhon, D., Schaeffer, G.: Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling. ACM Trans. Algorithms 4(2) (2008). (Preliminary version in SODA’05)
Gao, Z.: A pattern for the asymptotic number of rooted maps on surfaces. J. Comb. Theory, Ser. A 64, 246–264 (1993)
He, X., Kao, M.-Y., Lu, H.-I.: Linear-time succinct encodings of planar graphs via canonical orderings. SIAM J. Discrete Math. 12, 317–325 (1999)
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)
Keeler, K., Westbrook, J.: Short encodings of planar graph and maps. Discrete Appl. Math. 58, 239–252 (1995)
Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: SoCG, pp. 430–438 (2006)
Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: SoCG, pp. 80–89 (2001)
Lewiner, T., Lopes, H., Tavares, G.: Optimal discrete Morse functions for 2-manifolds. Comput. Geom. 26(3), 221–233 (2003)
Lewiner, T., Lopes, H., Rossignac, J., Vieira, A.W.: Efficient edgebreaker for surfaces of arbitrary topology. In: Sibgrapi, pp. 218–225 (2004)
Lopes, H., Rossignac, J., Safonova, A., Szymczak, A., Tavares, G.: Edgebreaker: a simple implementation for surfaces with handles. Comput. Graph. 27(4), 553–567 (2003)
Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins, Baltimore (2001)
Poulalhon, D., Schaeffer, G.: Optimal coding and sampling of triangulations. Algorithmica 46, 505–527 (2006)
Rossignac, J.: Edgebreaker: Connectivity compression for triangle meshes. Trans. Vis. Comput. Graph. 5, 47–61 (1999)
Schaeffer, G.: Conjugaison d’arbres et cartes combinatoires aléatoires. PhD thesis, Bordeaux I (1999)
Schnyder, W.: Planar graphs and poset dimension. Order 5, 323–343 (1989)
Schnyder, W.: Embedding planar graphs on the grid. In: SODA, pp. 138–148 (1990)
Tarjan, R.E.: Depth first search and linear graphs algorithms. SIAM J. Comput. 1, 146–160 (1972)
Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Process. Lett. 2, 160–161 (1974)
Turan, G.: On the succinct representation of graphs. Discrete Appl. Math. 8, 289–294 (1984)
Tutte, W.: A census of planar maps. Can. J. Math. 15, 249–271 (1963)
Vegter, G., Yap, C.-K.: Computational complexity of combinatorial surfaces. In: SoCG, pp. 102–111 (1990)
Author information
Authors and Affiliations
Corresponding author
Additional information
Extended version of the article appeared in the Proc. of the ACM SoCG 2008.
Part of the first author’s work was done during his visit to the CS Department of Université Libre de Bruxelles (Belgium).
Rights and permissions
About this article
Cite this article
Aleardi, L.C., Fusy, É. & Lewiner, T. Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding. Discrete Comput Geom 42, 489–516 (2009). https://doi.org/10.1007/s00454-009-9169-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-009-9169-z