{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:15:22Z","timestamp":1725563722141},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642157745"},{"type":"electronic","value":"9783642157752"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15775-2_48","type":"book-chapter","created":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T14:47:32Z","timestamp":1283352452000},"page":"561-572","source":"Crossref","is-referenced-by-count":3,"title":["Determining Edge Expansion and Other Connectivity Measures of Graphs of Bounded Genus"],"prefix":"10.1007","author":[{"given":"Viresh","family":"Patel","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"48_CR1","first-page":"329","volume-title":"FOCS 2007: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science","author":"C. Ambuhl","year":"2007","unstructured":"Ambuhl, C., Mastrolilli, M., Svensson, O.: Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling. In: FOCS 2007: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 329\u2013337. IEEE Computer Society, Los Alamitos (2007)"},{"issue":"2","key":"48_CR2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1145\/1502793.1502794","volume":"56","author":"S. Arora","year":"2009","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. J. ACM\u00a056(2), Art. 5, 37 (2009)","journal-title":"J. ACM"},{"key":"48_CR3","series-title":"Electron. Notes Discrete Math","first-page":"265","volume-title":"6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications","author":"P.S. Bonsma","year":"2007","unstructured":"Bonsma, P.S.: Linear time algorithms for finding sparsest cuts in various graph classes. In: 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. Electron. Notes Discrete Math, vol.\u00a0\u00a028, pp. 265\u2013272. Elsevier, Amsterdam (2007)"},{"key":"48_CR4","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/1542362.1542426","volume-title":"SCG 2009: Proceedings of the 25th annual symposium on Computational geometry","author":"E.W. Chambers","year":"2009","unstructured":"Chambers, E.W., Erickson, J., Nayyeri, A.: Minimum cuts and shortest homologous cycles. In: SCG 2009: Proceedings of the 25th annual symposium on Computational geometry, pp. 377\u2013385. ACM, New York (2009)"},{"key":"48_CR5","unstructured":"Erickson, J., Whittlesey, K.: Greedy optimal homotopy and homology generators. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1038\u20131046. ACM, New York (2005) (electronic)"},{"key":"48_CR6","series-title":"A Series of Books in the Mathematical Sciences","volume-title":"A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability. In: A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co, San Francisco (1979)"},{"key":"#cr-split#-48_CR7.1","unstructured":"Giblin, P.J.: Graphs, surfaces and homology, 2nd edn. Chapman & Hall, London (1981);"},{"key":"#cr-split#-48_CR7.2","unstructured":"An introduction to algebraic topology, Chapman and Hall Mathematics Series"},{"key":"#cr-split#-48_CR8.1","unstructured":"Gross, J.L., Tucker, T.W.: Topological graph theory. Dover Publications Inc., Mineola (2001);"},{"key":"#cr-split#-48_CR8.2","unstructured":"Reprint of the 1987 original [Wiley, New York; MR0898434 (88h:05034)] with a new preface and supplementary bibliography"},{"issue":"6","key":"48_CR9","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"J. ACM"},{"key":"#cr-split#-48_CR10.1","doi-asserted-by":"crossref","unstructured":"Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discrete Appl. Math.\u00a027(1-2), 113\u2013123 (1990);","DOI":"10.1016\/0166-218X(90)90133-W"},{"key":"#cr-split#-48_CR10.2","unstructured":"Computational algorithms, operations research and computer science, Burnaby, BC (1987)"},{"issue":"3","key":"48_CR11","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0095-8956(89)90029-4","volume":"47","author":"B. Mohar","year":"1989","unstructured":"Mohar, B.: Isoperimetric numbers of graphs. J. Combin. Theory Ser. B\u00a047(3), 274\u2013291 (1989)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"48_CR12","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1137\/S089548019529248X","volume":"12","author":"B. Mohar","year":"1999","unstructured":"Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math.\u00a012(1), 6\u201326 (1999) (electronic)","journal-title":"SIAM J. Discrete Math."},{"key":"48_CR13","series-title":"Johns Hopkins Studies in the Mathematical Sciences","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 Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)"},{"key":"48_CR14","doi-asserted-by":"crossref","unstructured":"Park, J.K., Phillips, C.A.: Finding minimum-quotient cuts in planar graphs. In: STOC, pp. 766\u2013775 (1993)","DOI":"10.1145\/167088.167284"},{"key":"48_CR15","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/129712.129735","volume-title":"STOC 1992: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing","author":"S.B. Rao","year":"1992","unstructured":"Rao, S.B.: Faster algorithms for finding small edge cuts in planar graphs. In: STOC 1992: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp. 229\u2013240. ACM, New York (1992)"},{"key":"48_CR16","unstructured":"Shmoys, D.M.: Approximation algorithms for NP-hard problems, ch.\u00a05. PWS Publishing Co., Boston (1997)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15775-2_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T03:15:33Z","timestamp":1685762133000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15775-2_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642157745","9783642157752"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15775-2_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}