{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T01:44:28Z","timestamp":1701135868670},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,4,22]],"date-time":"2009-04-22T00:00:00Z","timestamp":1240358400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00454-009-9169-z","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T14:45:00Z","timestamp":1240325100000},"page":"489-516","source":"Crossref","is-referenced-by-count":11,"title":["Schnyder Woods for Higher Genus Triangulated Surfaces, with Applications to Encoding"],"prefix":"10.1007","volume":"42","author":[{"given":"Luca Castelli","family":"Aleardi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c9ric","family":"Fusy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Lewiner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,4,22]]},"reference":[{"key":"9169_CR1","doi-asserted-by":"crossref","unstructured":"Barbay, J., Castelli-Aleardi, L., He, M., Munro, J.I.: Succinct representation of labeled graphs. In: ISAAC, pp. 316\u2013328 (2007)","DOI":"10.1007\/978-3-540-77120-3_29"},{"issue":"1","key":"9169_CR2","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.jcta.2008.05.005","volume":"116","author":"O. Bernardi","year":"2009","unstructured":"Bernardi, O., Bonichon, N.: Intervals in Catalan lattices and realizers of triangulations. J. Comb. Theory, Ser. A 116(1), 55\u201375 (2009)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9169_CR3","unstructured":"Bonichon, N.: Aspects algorithmiques et combinatoires des r\u00e9aliseurs des graphes plans maximaux. PhD thesis, Bordeaux I (2002)"},{"key":"9169_CR4","first-page":"499","volume-title":"STACS","author":"N. Bonichon","year":"2003","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N.: An information-theoretic upper bound of planar graphs using triangulation. In: STACS, pp. 499\u2013510. Springer, Berlin (2003)"},{"key":"9169_CR5","doi-asserted-by":"crossref","unstructured":"Bonichon, N., Gavoille, C., Labourel, A.: Edge partition of toroidal graphs into forests in linear time. In: ICGT, vol. 22, pp. 421\u2013425 (2005)","DOI":"10.1016\/j.endm.2005.06.065"},{"issue":"2","key":"9169_CR6","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/s00373-006-0647-2","volume":"22","author":"N. Bonichon","year":"2006","unstructured":"Bonichon, N., Gavoille, C., Hanusse, N., Poulalhon, D., Schaeffer, G.: Planar graphs, via well-orderly maps and trees. Graphs Comb. 22(2), 185\u2013202 (2006)","journal-title":"Graphs Comb."},{"key":"9169_CR7","unstructured":"Brehm, E.: 3-orientations and Schnyder-three tree decompositions. Master\u2019s thesis, Freie Universit\u00e4t Berlin (2000)"},{"issue":"2","key":"9169_CR8","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/s00454-006-1292-5","volume":"37","author":"S. Cabello","year":"2007","unstructured":"Cabello, S., Mohar, B.: Finding shortest non-separating and non-contractible cycles for topologically embedded graphs. Discrete Comput. Geom. 37(2), 213\u2013235 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9169_CR9","first-page":"134","volume-title":"WADS","author":"L. Castelli-Aleardi","year":"2005","unstructured":"Castelli-Aleardi, L., Devillers, O., Schaeffer, G.: Succinct representation of triangulations with a boundary. In: WADS, pp. 134\u2013145. Springer, Berlin (2005)"},{"key":"9169_CR10","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/j.tcs.2008.08.016","volume":"408","author":"L. Castelli-Aleardi","year":"2008","unstructured":"Castelli-Aleardi, L., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci. 408, 174\u2013187 (2008) (Preliminary version in SoCG\u201906)","journal-title":"Theor. Comput. Sci."},{"key":"9169_CR11","doi-asserted-by":"crossref","unstructured":"Chapuy, G.: Asymptotic enumeration of constellations and related families of maps on orientable surfaces. arXiv:0805.0352 (2008)","DOI":"10.1017\/S0963548309009808"},{"key":"9169_CR12","unstructured":"Chapuy, G., Marcus, M., Schaeffer, G.: A bijection for rooted maps on orientable surfaces. arXiv:0712.3649 (2007)"},{"key":"9169_CR13","unstructured":"Chiang, Y.-T., Lin, C.-C., Lu, H.-I.: Orderly spanning trees with applications to graph encoding and graph drawing. In: SODA, pp. 506\u2013515 (2001)"},{"key":"9169_CR14","doi-asserted-by":"crossref","unstructured":"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\u2013129 (1998)","DOI":"10.1007\/BFb0055046"},{"key":"9169_CR15","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0012-365X(00)00201-6","volume":"229","author":"H. Fraysseix de","year":"2001","unstructured":"de Fraysseix, H., de Mendez, P.O.: On topological aspects of orientations. Discrete Math. 229, 57\u201372 (2001)","journal-title":"Discrete Math."},{"key":"9169_CR16","unstructured":"de Mendez, P.O.: Orientations bipolaires. PhD thesis, Paris (1994)"},{"issue":"3","key":"9169_CR17","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s00454-004-1150-2","volume":"33","author":"E.C. Verdi\u00e8re de","year":"2005","unstructured":"de Verdi\u00e8re, E.C., Lazarus, F.: Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33(3), 507\u2013534 (2005). (Preliminary version in FOCS\u201902)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9169_CR18","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s00454-003-2948-z","volume":"31","author":"J. Erickson","year":"2004","unstructured":"Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37\u201359 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9169_CR19","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1023\/A:1010604726900","volume":"18","author":"S. Felsner","year":"2001","unstructured":"Felsner, S.: Convex drawings of planar graphs and the order dimension of 3-polytopes. Order 18, 19\u201337 (2001)","journal-title":"Order"},{"issue":"15","key":"9169_CR20","first-page":"24","volume":"11","author":"S. Felsner","year":"2004","unstructured":"Felsner, S.: Lattice structures from planar graphs. Electron. J. Comb. 11(15), 24 (2004)","journal-title":"Electron. J. Comb."},{"key":"9169_CR21","unstructured":"Fusy, \u00c9.: Combinatoire des cartes planaires et applications algorithmiques. PhD thesis, Ecole Polytechnique (2007)"},{"key":"9169_CR22","unstructured":"Fusy, \u00c9., 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\u201905)"},{"key":"9169_CR23","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1016\/0097-3165(93)90097-R","volume":"64","author":"Z. Gao","year":"1993","unstructured":"Gao, Z.: A pattern for the asymptotic number of rooted maps on surfaces. J. Comb. Theory, Ser. A 64, 246\u2013264 (1993)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9169_CR24","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/S0895480197325031","volume":"12","author":"X. He","year":"1999","unstructured":"He, X., Kao, M.-Y., Lu, H.-I.: Linear-time succinct encodings of planar graphs via canonical orderings. SIAM J. Discrete Math. 12, 317\u2013325 (1999)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"9169_CR25","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1007\/BF02086606","volume":"16","author":"G. Kant","year":"1996","unstructured":"Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4\u201332 (1996)","journal-title":"Algorithmica"},{"key":"9169_CR26","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0166-218X(93)E0150-W","volume":"58","author":"K. Keeler","year":"1995","unstructured":"Keeler, K., Westbrook, J.: Short encodings of planar graph and maps. Discrete Appl. Math. 58, 239\u2013252 (1995)","journal-title":"Discrete Appl. Math."},{"key":"9169_CR27","doi-asserted-by":"crossref","unstructured":"Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: SoCG, pp. 430\u2013438 (2006)","DOI":"10.1145\/1137856.1137919"},{"key":"9169_CR28","doi-asserted-by":"crossref","unstructured":"Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: SoCG, pp. 80\u201389 (2001)","DOI":"10.1145\/378583.378630"},{"issue":"3","key":"9169_CR29","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0925-7721(03)00014-2","volume":"26","author":"T. Lewiner","year":"2003","unstructured":"Lewiner, T., Lopes, H., Tavares, G.: Optimal discrete Morse functions for 2-manifolds. Comput. Geom. 26(3), 221\u2013233 (2003)","journal-title":"Comput. Geom."},{"key":"9169_CR30","doi-asserted-by":"crossref","unstructured":"Lewiner, T., Lopes, H., Rossignac, J., Vieira, A.W.: Efficient edgebreaker for surfaces of arbitrary topology. In: Sibgrapi, pp. 218\u2013225 (2004)","DOI":"10.1109\/SIBGRA.2004.1352964"},{"issue":"4","key":"9169_CR31","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1016\/S0097-8493(03)00102-X","volume":"27","author":"H. Lopes","year":"2003","unstructured":"Lopes, H., Rossignac, J., Safonova, A., Szymczak, A., Tavares, G.: Edgebreaker: a simple implementation for surfaces with handles. Comput. Graph. 27(4), 553\u2013567 (2003)","journal-title":"Comput. Graph."},{"key":"9169_CR32","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins, Baltimore (2001)"},{"key":"9169_CR33","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s00453-006-0114-8","volume":"46","author":"D. Poulalhon","year":"2006","unstructured":"Poulalhon, D., Schaeffer, G.: Optimal coding and sampling of triangulations. Algorithmica 46, 505\u2013527 (2006)","journal-title":"Algorithmica"},{"key":"9169_CR34","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1109\/2945.764870","volume":"5","author":"J. Rossignac","year":"1999","unstructured":"Rossignac, J.: Edgebreaker: Connectivity compression for triangle meshes. Trans. Vis. Comput. Graph. 5, 47\u201361 (1999)","journal-title":"Trans. Vis. Comput. Graph."},{"key":"9169_CR35","unstructured":"Schaeffer, G.: Conjugaison d\u2019arbres et cartes combinatoires al\u00e9atoires. PhD thesis, Bordeaux I (1999)"},{"key":"9169_CR36","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF00353652","volume":"5","author":"W. Schnyder","year":"1989","unstructured":"Schnyder, W.: Planar graphs and poset dimension. Order 5, 323\u2013343 (1989)","journal-title":"Order"},{"key":"9169_CR37","unstructured":"Schnyder, W.: Embedding planar graphs on the grid. In: SODA, pp. 138\u2013148 (1990)"},{"key":"9169_CR38","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth first search and linear graphs algorithms. SIAM J. Comput. 1, 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"9169_CR39","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1016\/0020-0190(74)90003-9","volume":"2","author":"R.E. Tarjan","year":"1974","unstructured":"Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Process. Lett. 2, 160\u2013161 (1974)","journal-title":"Inf. Process. Lett."},{"key":"9169_CR40","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0166-218X(84)90126-4","volume":"8","author":"G. Turan","year":"1984","unstructured":"Turan, G.: On the succinct representation of graphs. Discrete Appl. Math. 8, 289\u2013294 (1984)","journal-title":"Discrete Appl. Math."},{"key":"9169_CR41","doi-asserted-by":"crossref","first-page":"249","DOI":"10.4153\/CJM-1963-029-x","volume":"15","author":"W. Tutte","year":"1963","unstructured":"Tutte, W.: A census of planar maps. Can. J. Math. 15, 249\u2013271 (1963)","journal-title":"Can. J. Math."},{"key":"9169_CR42","doi-asserted-by":"crossref","unstructured":"Vegter, G., Yap, C.-K.: Computational complexity of combinatorial surfaces. In: SoCG, pp. 102\u2013111 (1990)","DOI":"10.1145\/98524.98546"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9169-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-009-9169-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-009-9169-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T22:05:45Z","timestamp":1684965945000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-009-9169-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4,22]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9169"],"URL":"https:\/\/doi.org\/10.1007\/s00454-009-9169-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,4,22]]}}}