{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:09Z","timestamp":1725664509184},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540613329"},{"type":"electronic","value":"9783540684619"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61332-3_149","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:33:02Z","timestamp":1330291982000},"page":"162-168","source":"Crossref","is-referenced-by-count":1,"title":["Efficient deterministic algorithms for embedding graphs on books"],"prefix":"10.1007","author":[{"given":"Farhad","family":"Shahrokhi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weiping","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"17_CR1","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. H. Spencer and P. Erd\u00f6s, The Probabilistic Method, Wiley and Sons, New York, 1992."},{"key":"17_CR2","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"B27","author":"F. Bernhart","year":"1979","unstructured":"F. Bernhart and B. Kainen, The book thickness of a graph, J. Combin. Theory, B27 (1979), 320\u2013331.","journal-title":"J. Combin. Theory"},{"key":"17_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"F. R. K. Chung","year":"1987","unstructured":"F. R. K. Chung, F. T. Leighton and A. Rosenberg, Embedding graphs in books: A layout problem with applications to VLSI design, SIAM J. Alg. Disc. Meth., 8 (1987) 33\u201358.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1145\/146637.146643","volume":"39","author":"L. Heath","year":"1992","unstructured":"L. Heath and S. Istrail, The page number of genus g graph is O(g), J. ACM\n39 (1992), 479\u2013500.","journal-title":"J. ACM"},{"key":"17_CR5","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0601025","volume":"1","author":"M. R. Garey","year":"1980","unstructured":"M. R. Garey, D. S. Johnson, G. L. Miller and C. H. Papadimitriou, The complexity of coloring circular arc graphs and chords, SIAM J. Alg. Disc. Meth., 1 (1980) 33\u201358.","journal-title":"SIAM J. Alg. Disc. Meth."},{"issue":"1","key":"17_CR6","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1006\/jagm.1994.1027","volume":"17","author":"S. M. Malitz","year":"1994","unstructured":"S. M. Malitz, On the page number of graphs, Journal of Algorithms, 17 (1) (1994), 71\u201384.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"17_CR7","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1006\/jagm.1994.1028","volume":"17","author":"S. M. Malitz","year":"1994","unstructured":"S. M. Malitz, Genus g graphs have pagenumber O(\u221ag), Journal of Algorithms, 17 (1) (1994), 85\u2013109.","journal-title":"Journal of Algorithms"},{"key":"17_CR8","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"D. W. Matula","year":"1983","unstructured":"D. W. Matula and L. L. Beck, Smallest-last ordering and clustering and graph coloring algorithms, J. ACM\n30 (1983), 417\u2013427.","journal-title":"J. ACM"},{"key":"17_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0021-9800(68)80081-X","volume":"4","author":"G. Szekeres","year":"1968","unstructured":"G. Szekeres and H. S. Wilf, An inequality for the chromatic number of a graph, J. Comb. Theory\n4 (1968), 1\u20133.","journal-title":"J. Comb. Theory"},{"key":"17_CR10","unstructured":"W. Unger, On the k-coloring of circle graphs, In Proc. 5th Annual Sympo. on Theoretical Aspects of Computer Science, 1988, 61\u201371."},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valient","year":"1979","unstructured":"L. Valient, On the complexity of counting the matching, Theoretical Computer Science\n8 (1979) 189\u2013201.","journal-title":"Theoretical Computer Science"},{"key":"17_CR12","unstructured":"A. Wigderson, The complexity of the Hamiltonian circuit problem for maximal planar graphs, EECS Report 298, Princeton University, 1982."},{"key":"17_CR13","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M. Yannakakis","year":"1989","unstructured":"M. Yannakakis, Embedding planar graphs in four pages, J. Computer and System Science\n38 (1989), 36\u201367.","journal-title":"J. Computer and System Science"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61332-3_149.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:31:32Z","timestamp":1619573492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61332-3_149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540613329","9783540684619"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-61332-3_149","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}