{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T02:08:43Z","timestamp":1778292523523,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540571551","type":"print"},{"value":"9783540479185","type":"electronic"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"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":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57155-8_251","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:05:33Z","timestamp":1330239933000},"page":"234-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the complexity of graph embeddings"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Saroja P.","family":"Kanchi","sequence":"additional","affiliation":[]},{"given":"Arkady","family":"Kanevsky","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"23_CR1","unstructured":"J. Chen, J. L. Gross and R.G. Rieper, Overlap matrices and imbedding distributions, Discrete Mathematics, to appear."},{"key":"23_CR2","unstructured":"H. Djidjev and J. Reif, An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs, Proc. 23rd Annual ACM Symposium on Theory of Computing, (1991), pp. 337\u2013347."},{"key":"23_CR3","first-page":"646","volume":"7","author":"J. Edmonds","year":"1960","unstructured":"J. Edmonds, A combinatorial representation for polyhedral surfaces. Not. Am. Math. Soc.7 (1960), pp. 646.","journal-title":"Not. Am. Math. Soc."},{"key":"23_CR4","unstructured":"I. S. Filotti, G. L. Miller, and J. H. Reif, On determining the genus of a graph in O(v\nO(g) steps, Proc. 11th Annual ACM Symposium on Theory of Computing, (1979), pp. 27\u201337."},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1145\/44483.44485","volume":"35-3","author":"M. L. Furst","year":"1988","unstructured":"M. L. Furst, J. L. Gross, and L. A. McGeoch, Finding a maximum-genus graph imbedding, J. of ACM35-3, (1988), pp. 523\u2013534.","journal-title":"J. of ACM"},{"key":"23_CR6","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979."},{"key":"23_CR7","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/jgt.3190110211","volume":"11-2","author":"J. L. Gross","year":"1987","unstructured":"J. L. Gross and M. L. Furst, Hierarchy of imbedding-distribution invariants of a graph, J. of Graph Theory11-2, (1987), pp. 205\u2013220.","journal-title":"J. of Graph Theory"},{"key":"23_CR8","unstructured":"J. L. Gross and T. W. Tucker, Topological Graph Theory, Wiley-Interscience, 1987."},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/jgt.3190150205","volume":"15-2","author":"J. L. Gross","year":"1991","unstructured":"J. L. Gross and R. G. Rieper, Local extrema in genus-stratified graphs, J. Graph Theory15-2, (1991) pp. 159\u2013171.","journal-title":"J. Graph Theory"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/BF01203357","volume":"38","author":"L. Heffter","year":"1891","unstructured":"L. Heffter, uber das Problem der Hachbargeibeite, Math. Annalen38, (1891), pp. 447\u2013508.","journal-title":"Math. Annalen"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"23_CR12","unstructured":"N. Robertson and P. D. Seymour, Graph minors \u2014a survey, Survey in Combinatorics, I. Anderson ed., Cambridge University Press, (1985), pp. 153\u2013171."},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/0196-6774(89)90006-0","volume":"10","author":"C. Thomassen","year":"1989","unstructured":"C. Thomassen, The graph genus problem is NP-complete, J. of Algorithms10, (1989), pp. 568\u2013576.","journal-title":"J. of Algorithms"},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/0095-8956(79)90058-3","volume":"26","author":"N. H. Xuong","year":"1979","unstructured":"N. H. Xuong, How to determine the maximum genus of a graph, J. Combinatorial Theory B26, (1979), pp. 217\u2013225.","journal-title":"J. Combinatorial Theory B"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T21:05:26Z","timestamp":1578517526000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_251"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_251","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}