×

Schnyder woods for higher genus triangulated surfaces, with applications to encoding. (English) Zbl 1210.05162

Summary: 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(g \log (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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C10 Planar graphs; geometric and topological aspects of graph theory
52B55 Computational aspects related to convexity
52B70 Polyhedral manifolds
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Software:

Edgebreaker
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Barbay, J., Castelli-Aleardi, L., He, M., Munro, J.I.: Succinct representation of labeled graphs. In: ISAAC, pp. 316-328 (2007) · Zbl 1193.05142
[2] Bernardi, O., Bonichon, N.: Intervals in Catalan lattices and realizers of triangulations. J. Comb. Theory, Ser. A 116(1), 55-75 (2009) · Zbl 1161.06001 · doi:10.1016/j.jcta.2008.05.005
[3] Bonichon, N.: Aspects algorithmiques et combinatoires des réaliseurs des graphes plans maximaux. PhD thesis, Bordeaux I (2002)
[4] Bonichon, N.; Gavoille, C.; Hanusse, N., An information-theoretic upper bound of planar graphs using triangulation, 499-510 (2003), Berlin · Zbl 1035.68514
[5] Bonichon, N., Gavoille, C., Labourel, A.: Edge partition of toroidal graphs into forests in linear time. In: ICGT, vol. 22, pp. 421-425 (2005) · Zbl 1200.05216
[6] 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) · Zbl 1099.05024 · doi:10.1007/s00373-006-0647-2
[7] Brehm, E.: 3-orientations and Schnyder-three tree decompositions. Master’s thesis, Freie Universität Berlin (2000)
[8] Cabello, S., Mohar, B.: Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Discrete Comput. Geom. 37(2), 213-235 (2007) · Zbl 1115.05019 · doi:10.1007/s00454-006-1292-5
[9] Castelli-Aleardi, L.; Devillers, O.; Schaeffer, G., Succinct representation of triangulations with a boundary, 134-145 (2005), Berlin · Zbl 1161.68396
[10] Castelli-Aleardi, L., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci. 408, 174-187 (2008) (Preliminary version in SoCG’06) · Zbl 1157.68066 · doi:10.1016/j.tcs.2008.08.016
[11] Chapuy, G.: Asymptotic enumeration of constellations and related families of maps on orientable surfaces. arXiv:0805.0352 (2008) · Zbl 1221.05204
[12] Chapuy, G., Marcus, M., Schaeffer, G.: A bijection for rooted maps on orientable surfaces. arXiv:0712.3649 (2007) · Zbl 1207.05087
[13] 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) · Zbl 0988.05029
[14] 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)
[15] de Fraysseix, H., de Mendez, P.O.: On topological aspects of orientations. Discrete Math. 229, 57-72 (2001) · Zbl 0980.05023 · doi:10.1016/S0012-365X(00)00201-6
[16] de Mendez, P.O.: Orientations bipolaires. PhD thesis, Paris (1994)
[17] 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) · Zbl 1076.57018 · doi:10.1007/s00454-004-1150-2
[18] Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37-59 (2004) · Zbl 1060.68129
[19] Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order 18, 19-37 (2001) · Zbl 0984.05029 · doi:10.1023/A:1010604726900
[20] Felsner, S.: Lattice structures from planar graphs. Electron. J. Comb. 11(15), 24 (2004) · Zbl 1056.05039
[21] Fusy, É.: Combinatoire des cartes planaires et applications algorithmiques. PhD thesis, Ecole Polytechnique (2007)
[22] 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) · Zbl 1451.05230
[23] Gao, Z.: A pattern for the asymptotic number of rooted maps on surfaces. J. Comb. Theory, Ser. A 64, 246-264 (1993) · Zbl 0792.05073 · doi:10.1016/0097-3165(93)90097-R
[24] 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) · Zbl 0937.05073 · doi:10.1137/S0895480197325031
[25] Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4-32 (1996) · Zbl 0851.68086 · doi:10.1007/BF02086606
[26] Keeler, K., Westbrook, J.: Short encodings of planar graph and maps. Discrete Appl. Math. 58, 239-252 (1995) · Zbl 0833.05025 · doi:10.1016/0166-218X(93)E0150-W
[27] Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: SoCG, pp. 430-438 (2006) · Zbl 1153.57304
[28] Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: SoCG, pp. 80-89 (2001) · Zbl 1378.65060
[29] Lewiner, T., Lopes, H., Tavares, G.: Optimal discrete Morse functions for 2-manifolds. Comput. Geom. 26(3), 221-233 (2003) · Zbl 1031.65031 · doi:10.1016/S0925-7721(03)00014-2
[30] Lewiner, T., Lopes, H., Rossignac, J., Vieira, A.W.: Efficient edgebreaker for surfaces of arbitrary topology. In: Sibgrapi, pp. 218-225 (2004)
[31] 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) · doi:10.1016/S0097-8493(03)00102-X
[32] Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins, Baltimore (2001) · Zbl 0979.05002
[33] Poulalhon, D., Schaeffer, G.: Optimal coding and sampling of triangulations. Algorithmica 46, 505-527 (2006) · Zbl 1106.68114 · doi:10.1007/s00453-006-0114-8
[34] Rossignac, J.: Edgebreaker: Connectivity compression for triangle meshes. Trans. Vis. Comput. Graph. 5, 47-61 (1999) · doi:10.1109/2945.764870
[35] Schaeffer, G.: Conjugaison d’arbres et cartes combinatoires aléatoires. PhD thesis, Bordeaux I (1999)
[36] Schnyder, W.: Planar graphs and poset dimension. Order 5, 323-343 (1989) · Zbl 0675.06001 · doi:10.1007/BF00353652
[37] Schnyder, W.: Embedding planar graphs on the grid. In: SODA, pp. 138-148 (1990) · Zbl 0786.05029
[38] Tarjan, R.E.: Depth first search and linear graphs algorithms. SIAM J. Comput. 1, 146-160 (1972) · Zbl 0251.05107 · doi:10.1137/0201010
[39] Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Process. Lett. 2, 160-161 (1974) · Zbl 0282.68018 · doi:10.1016/0020-0190(74)90003-9
[40] Turan, G.: On the succinct representation of graphs. Discrete Appl. Math. 8, 289-294 (1984) · Zbl 0551.68059 · doi:10.1016/0166-218X(84)90126-4
[41] Tutte, W.: A census of planar maps. Can. J. Math. 15, 249-271 (1963) · Zbl 0115.17305
[42] Vegter, G., Yap, C.-K.: Computational complexity of combinatorial surfaces. In: SoCG, pp. 102-111 (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.