{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:10:02Z","timestamp":1742591402654,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167662"},{"type":"electronic","value":"9783540387466"}],"license":[{"start":{"date-parts":[[1986,1,1]],"date-time":"1986-01-01T00:00:00Z","timestamp":504921600000},"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":[[1986]]},"DOI":"10.1007\/3-540-16766-8_20","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:53:51Z","timestamp":1330196031000},"page":"226-235","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Linear and book embeddings of graphs"],"prefix":"10.1007","author":[{"given":"Mihalis","family":"Yannakakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F. Bernhart","year":"1979","unstructured":"F. Bernhart and B. Kainen, \"The book thickness of a graph\", J. Combinatorial Theory B, 27, 320\u2013331, (1979).","journal-title":"J. Combinatorial Theory B"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"J. F. Buss, and P. W. Shor, \"On the pagenumber of planar graphs\", Proc. 16th Ann. ACM Symp. on Theory of Computing, 98\u2013100, (1984).","DOI":"10.1145\/800057.808670"},{"key":"20_CR3","unstructured":"F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, \"Diogenes: a methodology for designing fault-tolerant VLSI processor arrays\", 13th Int'l Conf. on Fault-tolerant Computing, 26\u201332, (1983)."},{"key":"20_CR4","unstructured":"F. R. K. Chung, F. T. Leighton, and A.L. Rosenberg, \"A graph layout problem with applications to VLSI design\", (1984)."},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"M. Chung, F. Makedon, I. H. Sudborough, J. Turner, \"Polynomial time algorithms for the min cut problem on degree restricted trees\". Proc. 23rd Annual Symp. on Foundations of Computer Science, 262\u2013271, (1982).","DOI":"10.1109\/SFCS.1982.85"},{"key":"20_CR6","unstructured":"D. Dolev and H. Trickey, \"Embedding a tree on a line\", IBM Technical Report, RJ3368, (1982)."},{"key":"20_CR7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/B978-0-12-417750-5.50011-7","volume-title":"Theory of Machines and Computations","author":"S. Even","year":"1971","unstructured":"S. Even, and A. Itai, \"Queues, stacks and graphs\", in Theory of Machines and Computations, Z. Kohavi and A. Paz, eds., Academic Press, NY, 71\u201386, (1971)."},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"A. Feller, \"Automatic layout of low-cost quick turnaround random-logic custom LSI devices\", Proc. 13th Annual Design Automation Conference, 79\u201385, (1976).","DOI":"10.1145\/800146.804799"},{"key":"20_CR9","unstructured":"M. J. Foster and H. T. Kung, \"Recognizing regular languages with programmable building blocks\", in VLSI-81, ed. J. P. Gray, Academic Press, 75\u201384, 1981."},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"R.A. Games, \"Optimal book embeddings of the FFT, Benes, and barrel shifter networks\", Third SIAM Conf. on Discrete Math., (1986).","DOI":"10.1007\/BF01840445"},{"key":"20_CR11","unstructured":"F. Gavril, \"Some NP-complete problems on graphs\", Proc. 11th Conf. on Information Sciences and Systems, John Hopkins University, 91\u201395, (1977)."},{"key":"20_CR12","doi-asserted-by":"crossref","first-page":"216","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 arcs and chords\", SIAM J. on Alg. and Disc. Meth., 1, 216\u2013227, (1980).","journal-title":"SIAM J. on Alg. and Disc. Meth."},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, 1980.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"L. Heath, \"Embedding planar graphs in seven pages\", Proc. 25th Ann. Symp. on Foundations of Computer Science, 74\u201383, (1984).","DOI":"10.1109\/SFCS.1984.715903"},{"key":"20_CR15","unstructured":"L. Heath, \"Algorithms for embedding graphs in books\", Third SIAM Conf. on Discrete Math., (1986)."},{"key":"20_CR16","unstructured":"S. Istrail, \"An algorithm for embedding planar graphs in six pages\", private communication, (1985)."},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"T. Lengauer, \"Upper and lower bounds on the complexity of the min-cut linear arrangement problem on trees\", SIAM J. Alg. Disc. Meth., (1982).","DOI":"10.1137\/0603010"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"F. Makedon, I. H. Sudborough, \"Minimizing width in linear layouts\", Proc. 10th Intl. Coll. on Automata, Languages and Programming, 478\u2013490, (1983).","DOI":"10.1007\/BFb0036931"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"F. Makedon, C. H. Papadimitriou, I. H. Sudborough, \"Topological bandwidth\", SIAM J. Alg. Disc. Meth., (1985).","DOI":"10.1137\/0606044"},{"key":"20_CR20","first-page":"217","volume":"1","author":"G. Persky","year":"1977","unstructured":"G. Persky, D. Deutsch, D. Schweikert, \"LTX-A minicomputer-based system for automated LSI layout\", J. Design Automation and Fault Tolerant Computing,1, 217\u2013255, (1977).","journal-title":"J. Design Automation and Fault Tolerant Computing"},{"key":"20_CR21","doi-asserted-by":"crossref","first-page":"902","DOI":"10.1109\/TC.1983.1676134","volume":"C-32","author":"A. L. Rosenberg","year":"1983","unstructured":"A. L. Rosenberg, \"The Diogenes Approach to testable fault-tolerant arrays of processors\", IEEE Trans. on Computing, C-32, 902\u2013910, (1983).","journal-title":"IEEE Trans. on Computing"},{"key":"20_CR22","unstructured":"P. Rosenstiehl, R. E. Tarjan, \"Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations\", (1982)."},{"key":"20_CR23","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321694.321704","volume":"19","author":"R. E. Tarjan","year":"1972","unstructured":"R. E. Tarjan, \"Sorting using networks of queues and stacks\", J. Assoc. Comp. Mach., 19, 341\u2013346, (1972).","journal-title":"J. Assoc. Comp. Mach."},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"A. Weinberger, \"Large scale integration of MOS complex logic\", IEEE J. Solid State Circuits, 182\u2013190, (1967).","DOI":"10.1109\/JSSC.1967.1049816"},{"key":"20_CR25","unstructured":"A. Wigderson, \"The complexity of the Hamiltonian circuit problem for planar graphs\", Princeton Univ. Tech. Report."},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, \"A polynomial algorithm for the min-cut linear arrangement of trees\", J. ACM, 950\u2013988, (1985).","DOI":"10.1145\/4221.4228"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, \"Four pages are necessary and sufficient for planar graphs\", Proc. 18th ACM Symp. on Theory of Computing, (1986).","DOI":"10.1145\/12130.12141"}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16766-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:29:29Z","timestamp":1742588969000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16766-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167662","9783540387466"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-16766-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}