{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:47Z","timestamp":1725664547543},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540594086"},{"type":"electronic","value":"9783540492450"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59408-6_64","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T12:15:49Z","timestamp":1330258549000},"page":"360-363","source":"Crossref","is-referenced-by-count":3,"title":["Embedding graphs in the torus in linear time"],"prefix":"10.1007","author":[{"given":"Martin","family":"Juvan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jo\u017ee","family":"Marin\u010dek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bojan","family":"Mohar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth, G. S. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-trees, J. Comput. System Sci. 13 (1976) 335\u2013379.","journal-title":"J. Comput. System Sci."},{"key":"28_CR2","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0022-0000(80)90062-8","volume":"20","author":"I. S. Filotti","year":"1980","unstructured":"I. S. Filotti, An algorithm for imbedding cubic graphs in the torus, J. Comput. System Sci. 20 (1980) 255\u2013276.","journal-title":"J. Comput. System Sci."},{"key":"28_CR3","doi-asserted-by":"crossref","unstructured":"I. S. Filotti, G. L. Miller, J. Reif, On determining the genus of a graph in O(\u03c5o(g)) steps, in \u201cProceedings, 11th Annu. ACM STOC, Atlanta, Georgia, 1979,\u201d pp. 27\u201337.","DOI":"10.1145\/800135.804395"},{"key":"28_CR4","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft, R. E. Tarjan, Dividing a graph into triconnected components, SIAM J. Comput. 2 (1973) 135\u2013158.","journal-title":"SIAM J. Comput."},{"key":"28_CR5","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. E. Hopcroft","year":"1974","unstructured":"J. E. Hopcroft, R. E. Tarjan, Efficient planarity testing, J. ACM 21 (1974) 549\u2013568.","journal-title":"J. ACM"},{"key":"28_CR6","unstructured":"M. Juvan, J. Marin\u010dek, B. Mohar, Elimination of local bridges, submitted."},{"key":"28_CR7","unstructured":"M. Juvan, J. Marin\u010dek, B. Mohar, Obstructions for simple embeddings, submitted."},{"key":"28_CR8","unstructured":"M. Juvan, J. Marin\u010dek, B. Mohar, Embedding a graph into the torus in linear time, submitted."},{"key":"28_CR9","unstructured":"M. Juvan, J. Marin\u010dek, B. Mohar, Efficient algorithm for embedding graphs in arbitrary surfaces, in preparation."},{"key":"28_CR10","unstructured":"M. Juvan, B. Mohar, Extending 2-restricted partial embeddings of graphs, submitted."},{"key":"28_CR11","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0095-8956(90)90121-F","volume":"48","author":"N. Robertson","year":"1990","unstructured":"N. Robertson, P. D. Seymour, Graph minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory, Ser. B 48 (1990) 255\u2013288.","journal-title":"J. Combin. Theory, Ser. B"},{"key":"28_CR12","unstructured":"N. Robertson, P. D. Seymour, Graph minors. XIII. The disjoint paths problem, preprint, revision of February 1992."},{"key":"28_CR13","unstructured":"N. Robertson, P. D. Seymour, Graph minors. XXI. Graphs with unique linkages, preprint, 1992."},{"key":"28_CR14","unstructured":"N. Robertson, P. D. Seymour, Graph minors. XXII. Irrelevant vertices in linkage problems, preprint, 1992."},{"key":"28_CR15","doi-asserted-by":"crossref","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. Algorithms 10 (1989) 568\u2013576.","journal-title":"J. Algorithms"},{"key":"28_CR16","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0167-5060(08)70719-2","volume":"6","author":"S. G. Williamson","year":"1980","unstructured":"S. G. Williamson, Embedding graphs in the plane \u2014 algorithmic aspects, Ann. Discrete Math. 6 (1980) 349\u2013384.","journal-title":"Ann. Discrete Math."},{"key":"28_CR17","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1145\/1634.322451","volume":"31","author":"S. G. Williamson","year":"1984","unstructured":"S. G. Williamson, Depth-first search and Kuratowski subgraphs, J. ACM 31 (1984) 681\u2013693.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59408-6_64.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:27:05Z","timestamp":1605630425000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59408-6_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540594086","9783540492450"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-59408-6_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}