{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T08:25:55Z","timestamp":1724660755171},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00454-015-9679-9","type":"journal-article","created":{"date-parts":[[2015,4,3]],"date-time":"2015-04-03T06:32:33Z","timestamp":1428042753000},"page":"587-620","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Discrete Systolic Inequalities and Decompositions of Triangulated Surfaces"],"prefix":"10.1007","volume":"53","author":[{"given":"\u00c9ric","family":"Colin\u00a0de\u00a0Verdi\u00e8re","sequence":"first","affiliation":[]},{"given":"Alfredo","family":"Hubard","sequence":"additional","affiliation":[]},{"given":"Arnaud","family":"de Mesmay","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,2]]},"reference":[{"issue":"1","key":"9679_CR1","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s00039-012-0147-x","volume":"22","author":"F Balacheff","year":"2012","unstructured":"Balacheff, F., Parlier, H., Sabourau, S.: Short loop decompositions of surfaces and the geometry of Jacobians. Geom. Funct. Anal. 22(1), 37\u201373 (2012)","journal-title":"Geom. Funct. Anal."},{"key":"9679_CR2","unstructured":"Boissonnat, J.-D., Dyer, R., Ghosh, A.: Delaunay triangulations of manifolds. arXiv:1311.0117 (2013)"},{"issue":"1","key":"9679_CR3","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4310\/jdg\/1102536712","volume":"68","author":"R Brooks","year":"2004","unstructured":"Brooks, R., Makover, E.: Random construction of Riemann surfaces. J. Differ. Geom. 68(1), 121\u2013157 (2004)","journal-title":"J. Differ. Geom."},{"key":"9679_CR4","volume-title":"Geometry and Spectra of Compact Riemann Surfaces. Progress in Mathematics","author":"P Buser","year":"1992","unstructured":"Buser, P.: Geometry and Spectra of Compact Riemann Surfaces. Progress in Mathematics, vol. 106. Birkh\u00e4user, Basel (1992)"},{"key":"9679_CR5","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF01232233","volume":"117","author":"P Buser","year":"1994","unstructured":"Buser, P., Sarnak, P.: On the period matrix of a Riemann surface of large genus (with an appendix by J.H. Conway and N.J.A. Sloane). Invent. Math. 117, 27\u201356 (1994)","journal-title":"Invent. Math."},{"issue":"2","key":"9679_CR6","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":"9679_CR7","doi-asserted-by":"crossref","unstructured":"Cabello, S., Colin de Verdi\u00e8re, \u00c9., Lazarus, F.: Algorithms for the edge-width of an embedded graph. Comput. Geom. 45, 215\u2013224 (2012)","DOI":"10.1016\/j.comgeo.2011.12.002"},{"issue":"4","key":"9679_CR8","doi-asserted-by":"crossref","first-page":"1542","DOI":"10.1137\/120864271","volume":"42","author":"S Cabello","year":"2013","unstructured":"Cabello, S., Chambers, E.W., Erickson, J.: Multiple-source shortest paths in embedded graphs. SIAM J. Comput. 42(4), 1542\u20131571 (2013)","journal-title":"SIAM J. Comput."},{"key":"9679_CR9","doi-asserted-by":"crossref","unstructured":"Chambers, E.W., Colin de Verdi\u00e8re, \u00c9., Erickson, J., Lazarus, F., Whittlesey, Kim: Splitting (complicated) surfaces is hard. Comput. Geom. 41(1\u20132), 94\u2013110 (2008)","DOI":"10.1016\/j.comgeo.2007.10.010"},{"key":"9679_CR10","doi-asserted-by":"crossref","unstructured":"Chambers, E., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: Proceedings of the 25th Annual Symposium on Computational Geometry (SOCG), pp. 377\u2013385. ACM, New York (2009)","DOI":"10.1145\/1542362.1542426"},{"issue":"6","key":"9679_CR11","doi-asserted-by":"crossref","first-page":"1605","DOI":"10.1137\/090766863","volume":"41","author":"EW Chambers","year":"2012","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Homology flows, cohomology cuts. SIAM J. Comput. 41(6), 1605\u20131634 (2012)","journal-title":"SIAM J. Comput."},{"key":"9679_CR12","unstructured":"Colin de Verdi\u00e8re, \u00c9.: Topological algorithms for graphs on surfaces. PhD thesis, \u00c9cole normale sup\u00e9rieure, 2012. Habilitation thesis, available at http:\/\/www.di.ens.fr\/colin\/"},{"issue":"8","key":"9679_CR13","doi-asserted-by":"crossref","first-page":"3784","DOI":"10.1137\/090761653","volume":"39","author":"\u00c9 Colin de Verdi\u00e8re","year":"2010","unstructured":"Colin de Verdi\u00e8re, \u00c9., Erickson, J.: Tightening nonsimple paths and cycles on surfaces. SIAM J. Comput. 39(8), 3784\u20133813 (2010)","journal-title":"SIAM J. Comput."},{"key":"9679_CR14","doi-asserted-by":"crossref","unstructured":"Colin de Verdi\u00e8re, \u00c9., Lazarus, F.: Optimal pants decompositions and shortest homotopic cycles on an orientable surface. J. ACM 54(4): Article 18 (2007)","DOI":"10.1145\/1255443.1255446"},{"key":"9679_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2201-7","volume-title":"Riemannian Geometry","author":"MP Carmo do","year":"1992","unstructured":"do Carmo, M.P.: Riemannian Geometry. Birkh\u00e4user, Boston (1992)"},{"issue":"5","key":"9679_CR16","doi-asserted-by":"crossref","first-page":"1393","DOI":"10.1111\/j.1467-8659.2008.01279.x","volume":"27","author":"R Dyer","year":"2008","unstructured":"Dyer, R., Zhang, H., M\u00f6ller, T.: Surface sampling and the intrinsic Voronoi diagram. Comput. Graph. Forum 27(5), 1393\u20131402 (2008)","journal-title":"Comput. Graph. Forum"},{"issue":"3","key":"9679_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1541885.1541890","volume":"5","author":"D Eppstein","year":"2009","unstructured":"Eppstein, D.: Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition. ACM Trans. Algorithms 5(3), 1\u201324 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"9679_CR18","doi-asserted-by":"crossref","unstructured":"Erickson, J.: Combinatorial optimization of cycles and bases. In: Zomorodian, A. (ed.) Computational Topology. In: Proceedings of Symposia in Applied Mathematics. American Mathematical Society, Providence, RI (2012)","DOI":"10.1090\/psapm\/070\/591"},{"issue":"1","key":"9679_CR19","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":"9679_CR20","doi-asserted-by":"crossref","unstructured":"Erickson, J., Nayyeri, A.: Computing replacement paths in surface-embedded graphs. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1347\u20131354 (2011)","DOI":"10.1137\/1.9781611973082.103"},{"key":"9679_CR21","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1038\u20131046 (2005)"},{"issue":"4","key":"9679_CR22","doi-asserted-by":"crossref","first-page":"912","DOI":"10.1007\/s00454-010-9241-8","volume":"44","author":"J Erickson","year":"2010","unstructured":"Erickson, J., Worah, P.: Computing the shortest essential cycle. Discrete Comput. Geom. 44(4), 912\u2013930 (2010)","journal-title":"Discrete Comput. Geom."},{"key":"9679_CR23","doi-asserted-by":"crossref","unstructured":"Erickson, J., Fox, K., Nayyeri, A.: Global minimum cuts in surface embedded graphs. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1309\u20131318 (2012)","DOI":"10.1137\/1.9781611973099.103"},{"key":"9679_CR24","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1090\/conm\/311\/05451","volume-title":"Complex Manifolds and Hyperbolic Geometry. Contemporary Mathematics","author":"A Gamburd","year":"2002","unstructured":"Gamburd, A., Makover, E.: On the genus of a random riemann surface. Complex Manifolds and Hyperbolic Geometry. Contemporary Mathematics, vol. 311, pp. 133\u2013140. American Mathematical Society, Providence, RI (2002)"},{"key":"9679_CR25","unstructured":"Geelen, J., Huynh, T., Richter, R.B.: Explicit bounds for graph minors. arxiv:1305.1451 (2013)"},{"key":"9679_CR26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4310\/jdg\/1214509283","volume":"18","author":"M Gromov","year":"1983","unstructured":"Gromov, M.: Filling Riemannian manifolds. J. Differ. Geom. 18, 1\u2013147 (1983)","journal-title":"J. Differ. Geom."},{"key":"9679_CR27","unstructured":"Gromov, M.: Systoles and intersystolic inequalities. In: Actes de la table ronde de g\u00e9om\u00e9trie diff\u00e9rentielle, pp. 291\u2013362 (1992)"},{"issue":"1991","key":"9679_CR28","first-page":"9","volume":"61","author":"M Gromov","year":"1994","unstructured":"Gromov, M.: Sign and geometric meaning of curvature. Rend. Semin. Mat. Fis. Milano 61(1991), 9\u2013123 (1994)","journal-title":"Rend. Semin. Mat. Fis. Milano"},{"key":"9679_CR29","unstructured":"Guskov, I., Wood, Z.J.: Topological noise removal. In: Proceedings of Graphics Interface, pp. 19\u201326 (2001)"},{"key":"9679_CR30","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1007\/s00039-011-0131-x","volume":"21","author":"L Guth","year":"2011","unstructured":"Guth, L., Parlier, H., Young, R.: Pants decompositions of random surfaces. Geom. Funct. Anal. 21, 1069\u20131090 (2011)","journal-title":"Geom. Funct. Anal."},{"key":"9679_CR31","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/130","volume-title":"Isometric Embedding of Riemannian Manifolds in Euclidean Spaces. Mathematical Surveys and Monographs","author":"Q Han","year":"2006","unstructured":"Han, Q., Hong, J.-X.: Isometric Embedding of Riemannian Manifolds in Euclidean Spaces. Mathematical Surveys and Monographs, vol. 130. American Mathematical Society, Providence, RI (2006)"},{"key":"9679_CR32","unstructured":"Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002). Available at http:\/\/www.math.cornell.edu\/hatcher\/"},{"issue":"2","key":"9679_CR33","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1137\/0401020","volume":"1","author":"JP Hutchinson","year":"1988","unstructured":"Hutchinson, J.P.: On short noncontractible cycles in embedded graphs. SIAM J. Discrete Math. 1(2), 185\u2013192 (1988)","journal-title":"SIAM J. Discrete Math."},{"key":"9679_CR34","doi-asserted-by":"crossref","DOI":"10.1090\/surv\/137","volume-title":"Systolic Geometry and Topology. Mathematical Surveys and Monographs","author":"M Katz","year":"2007","unstructured":"Katz, M.: Systolic Geometry and Topology. Mathematical Surveys and Monographs, vol. 137. American Mathematical Society, Providence, RI (2007). (With an appendix by J. Solomon.)"},{"issue":"4","key":"9679_CR35","doi-asserted-by":"crossref","first-page":"1209","DOI":"10.1017\/S0143385704001014","volume":"25","author":"MG Katz","year":"2005","unstructured":"Katz, M.G., Sabourau, S.: Entropy of systolically extremal surfaces and asymptotic bounds. Ergodic Theory Dyn. Syst. 25(4), 1209\u20131220 (2005)","journal-title":"Ergodic Theory Dyn. Syst."},{"key":"9679_CR36","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BF02565940","volume":"34","author":"MA Kervaire","year":"1960","unstructured":"Kervaire, M.A.: A manifold which does not admit any differentiable structure. Comment. Math. Helv. 34, 257\u2013270 (1960)","journal-title":"Comment. Math. Helv."},{"key":"9679_CR37","doi-asserted-by":"crossref","DOI":"10.1515\/9783110905120","volume-title":"Riemannian Geometry. Philosophie und Wissenschaft","author":"W Klingenberg","year":"1995","unstructured":"Klingenberg, W.: Riemannian Geometry. Philosophie und Wissenschaft. de Gruyter, Berlin (1995)"},{"key":"9679_CR38","unstructured":"Kowalick, R.: Discrete systolic inequalities. PhD Thesis, Ohio State University (2013). http:\/\/rave.ohiolink.edu\/etdc\/view?acc_num=osu1384873457"},{"key":"9679_CR39","doi-asserted-by":"crossref","unstructured":"Kutz, M.: Computing shortest non-trivial cycles on orientable surfaces of bounded genus in almost linear time. In: Proceedings of the 22nd Annual Symposium on Computational Geometry (SOCG), pp. 430\u2013438. American Mathematical Society, Providence, RI (2006)","DOI":"10.1145\/1137856.1137919"},{"key":"9679_CR40","doi-asserted-by":"crossref","unstructured":"Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: Proceedings of the 17th Annual Symposium on Computational Geometry (SOCG), pp. 80\u201389. American Mathematical Society, Providence, RI (2001)","DOI":"10.1145\/378583.378630"},{"key":"9679_CR41","doi-asserted-by":"crossref","unstructured":"Lee, J.R., Sidiropoulos, A.: Genus and the geometry of the cut graph. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 193\u2013201 (2010)","DOI":"10.1137\/1.9781611973075.18"},{"key":"9679_CR42","unstructured":"Leibon, G.: Random Delaunay Triangulations, the Thurston-Andreev Theorem and Metric Uniformization. PhD Thesis, University of California at San Diego (1999). Available on arXiv:math\/0011016v1"},{"key":"9679_CR43","doi-asserted-by":"crossref","unstructured":"L\u00e9vy, B., Mallet, J.-L.: Non-distorted texture mapping for sheared triangulated meshes. In: Proceedings of the 25th Annual Conference on Computer Graphics (SIGGRAPH), pp. 343\u2013352 (1998)","DOI":"10.1145\/280814.280930"},{"key":"9679_CR44","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1109\/TVCG.2008.200","volume":"15","author":"X Li","year":"2009","unstructured":"Li, X., Xianfeng, G., Qin, H.: Surface mapping using consistent pants decomposition. IEEE Trans. Vis. Comput. Graph. 15, 558\u2013571 (2009)","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"9679_CR45","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s10711-010-9528-1","volume":"151","author":"E Makover","year":"2011","unstructured":"Makover, E., McGowan, J.: The length of closed geodesics on random Riemann surfaces. Geom. Dedicata 151, 207\u2013220 (2011)","journal-title":"Geom. Dedicata"},{"key":"9679_CR46","first-page":"472","volume-title":"Graph Drawing. Lecture Notes in Computer Science","author":"J Matou\u0161ek","year":"2013","unstructured":"Matou\u0161ek, J., Sedgwick, E., Tancer, M., Wagner, U.: Untangling two systems of noncrossing curves. In: Wismath, S., Wolff, A. (eds.) Graph Drawing. Lecture Notes in Computer Science, vol. 8242, pp. 472\u2013483. Springer, Cham (2013)"},{"issue":"4","key":"9679_CR47","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF02579144","volume":"4","author":"BD McKay","year":"1984","unstructured":"McKay, B.D., Wormald, N.C.: Automorphisms of random graphs with specified vertices. Combinatorica 4(4), 325\u2013338 (1984)","journal-title":"Combinatorica"},{"key":"9679_CR48","doi-asserted-by":"crossref","unstructured":"Piponi, D., Borshukov, G.: Seamless texture mapping of subdivision surfaces by model pelting and texture blending. In: Proceedings of the 27th Annual Conference on Computer Graphics (SIGGRAPH), pp. 471\u2013478 (2000)","DOI":"10.1145\/344779.344990"},{"issue":"3","key":"9679_CR49","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1002\/rsa.20080","volume":"28","author":"N Pippenger","year":"2006","unstructured":"Pippenger, N., Schleich, K.: Topological characteristics of random triangulated surfaces. Random Struct. Algorithms 28(3), 247\u2013288 (2006)","journal-title":"Random Struct. Algorithms"},{"key":"9679_CR50","unstructured":"Poon, S.-H., Thite, S.: Pants decomposition of the punctured plane. Preliminary version in Abstracts of the European Workshop on Computational Geometry (2006). arXiv:cs.CG\/0602080"},{"issue":"2","key":"9679_CR51","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0403024","volume":"3","author":"TM Przytycka","year":"1990","unstructured":"Przytycka, T.M., Przytycki, J.H.: On a lower bound for short noncontractible cycles in embedded graphs. SIAM J. Discrete Math. 3(2), 281\u2013293 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"9679_CR52","volume-title":"Graph Structure Theory. Contemporary Mathematics","author":"TM Przytycka","year":"1993","unstructured":"Przytycka, T.M., Przytycki, J.H.: Surface triangulations without short noncontractible cycles. In: Robertson, N., Seymour, P. (eds.) Graph Structure Theory. Contemporary Mathematics, vol. 147. American Mathematical Society, Providence, RI (1993)"},{"key":"9679_CR53","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0012-365X(96)00132-X","volume":"173","author":"TM Przytycka","year":"1997","unstructured":"Przytycka, T.M., Przytycki, J.H.: A simple construction of high representativity triangulations. Discrete Math. 173, 209\u2013228 (1997)","journal-title":"Discrete Math."},{"key":"9679_CR54","doi-asserted-by":"crossref","first-page":"55","DOI":"10.2140\/pjm.1952.2.55","volume":"2","author":"PM Pu","year":"1952","unstructured":"Pu, P.M.: Some inequalities in certain nonorientable riemannian manifolds. Pac. J. Math. 2, 55\u201371 (1952)","journal-title":"Pac. J. Math."},{"key":"9679_CR55","unstructured":"Read, R.C.: Some enumeration problems in graph theory. PhD Thesis, University of London (1958)"},{"key":"9679_CR56","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/0095-8956(88)90070-6","volume":"45","author":"N Robertson","year":"1988","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VII. Disjoint paths on a surface. J. Comb. Theory Ser. B 45, 212\u2013254 (1988)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9679_CR57","doi-asserted-by":"crossref","first-page":"35","DOI":"10.4171\/CMH\/117","volume":"83","author":"S Sabourau","year":"2008","unstructured":"Sabourau, S.: Asymptotic bounds for separating systoles on surfaces. Comment. Math. Helv. 83, 35\u201354 (2008)","journal-title":"Comment. Math. Helv."},{"key":"9679_CR58","volume-title":"A Comprehensive Introduction to Differential Geometry","author":"M Spivak","year":"1999","unstructured":"Spivak, M.: A Comprehensive Introduction to Differential Geometry, vol. II. Publish or Perish Press, Boston (1999)"},{"key":"9679_CR59","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-0110-3","volume-title":"Classical Topology and Combinatorial Group Theory","author":"J Stillwell","year":"1980","unstructured":"Stillwell, J.: Classical Topology and Combinatorial Group Theory. Springer, New York (1980)"},{"issue":"2","key":"9679_CR60","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1145\/990002.990007","volume":"23","author":"Z Wood","year":"2004","unstructured":"Wood, Z., Hoppe, H., Desbrun, M., Schr\u00f6der, P.: Removing excess topology from isosurfaces. ACM Trans. Graph. 23(2), 190\u2013208 (2004)","journal-title":"ACM Trans. Graph."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9679-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9679-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9679-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T21:17:48Z","timestamp":1566508668000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9679-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9679"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9679-9","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}