{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:20Z","timestamp":1759638560629,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540102915"},{"type":"electronic","value":"9783540384359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10291-4_12","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:09:10Z","timestamp":1330189750000},"page":"150-176","source":"Crossref","is-referenced-by-count":19,"title":["Issues in the study of graph embeddings"],"prefix":"10.1007","author":[{"given":"Arnold L.","family":"Rosenberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"12_CR1","unstructured":"R. Aleliunas and A.L. Rosenberg: On embedding rectangular grids in square grids. Submitted for publication, 1980."},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"A. Borodin, M.J. Fischer, D. Kirkpatrick, N.A. Lynch, M. Tompa: A time-space tradeoff for sorting on nonoblivious machines. Proc. 20th FOCS Symp., 1979, 319\u2013327.","DOI":"10.1109\/SFCS.1979.4"},{"key":"12_CR3","unstructured":"R.P. Brent and H.T. Kung: On the area of binary tree layouts. Australian National University Report TR-CS-79-07, 1979."},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"A. Cobham: The recognition problem for the set of perfect squares. Proc. 7th SWAT Symp., 1966, 78\u201387.","DOI":"10.1109\/SWAT.1966.30"},{"key":"12_CR5","unstructured":"F.R.K. Chung and R.L. Graham: On universal graphs for spanning trees. Unpublished typescript, 1979."},{"key":"12_CR6","unstructured":"F.R.K. Chung and R.L. Graham: Unpublished typescript, 1979."},{"key":"12_CR7","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1145\/359361.359447","volume":"21","author":"R. A. DeMillo","year":"1978","unstructured":"R.A. DeMillo, S.C. Eisenstat and R.J. Lipton: Preserving average proximity in arrays. C.ACM 21 (1978), 228\u2013231.","journal-title":"C.ACM"},{"key":"12_CR8","unstructured":"\u2014: On small universal data structures and related combinatorial problems. Proc. Johns Hopkins Conf. on Inf. Sci. and Syst., 1978, 408\u2013411."},{"key":"12_CR9","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. R. Garey","year":"1978","unstructured":"M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth: Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34 (1978), 477\u2013495.","journal-title":"SIAM J. Appl. Math."},{"key":"12_CR10","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M.R. Garey, D.S. Johnson and L.J. Stockmeyer: Some simplified NP-complete graph problems. Theor. Comp. Sci. 1 (1976), 237\u2013267.","journal-title":"Theor. Comp. Sci."},{"key":"12_CR11","first-page":"713","volume":"4","author":"M. K. Gol'dberg","year":"1968","unstructured":"M.K. Gol'dberg and \u00c9.M. Livshits: On minimal universal trees. Math. Notes of Acad. Sci. USSR 4 (1968), 713\u2013717.","journal-title":"Math. Notes of Acad. Sci. USSR"},{"key":"12_CR12","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/S0021-9800(66)80059-5","volume":"1","author":"L. H. Harper","year":"1966","unstructured":"L.H. Harper: Optimal numberings and isoperimetric problems on graphs. J. Comb. Th. 1 (1966), 385\u2013393.","journal-title":"J. Comb. Th."},{"key":"12_CR13","unstructured":"J-W.Hong, K. Mehlhorn, and A.L. Rosenberg: Cost tradeoffs in graph embeddings. In preparation."},{"key":"12_CR14","unstructured":"J-W. Hong and A.L. Rosenberg: Graphs that are similar to binary trees. Submitted for publication, 1980."},{"key":"12_CR15","first-page":"423","volume-title":"High Speed Computer and Algorithm Optimization","author":"H. T. Kung","year":"1977","unstructured":"H.T. Kung and D. Stevenson: A software technique for reducing the routing time on a parallel computer with a fixed interconnection network. In High Speed Computer and Algorithm Optimization, Academic Press, New York (1977), 423\u2013433."},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"C.E. Leiserson: Area-efficient graph layouts. Unpublished typescript, 1979.","DOI":"10.1109\/SFCS.1980.13"},{"key":"12_CR17","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/321978.321990","volume":"23","author":"R. J. Lipton","year":"1976","unstructured":"R.J. Lipton, S.C. Eisenstat and R.A. DeMillo: Space and time hierarchies for classes of control structures and data structures. J.ACM 23 (1976), 720\u2013732.","journal-title":"J.ACM"},{"key":"12_CR18","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R.J. Lipton and R.E. Tarjan: A separator theorem for planar graphs. SIAM J. Appl. Math. 36 (1979), 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"\u2014: Applications of a planar separator theorem. Proc. 18th FOCS Symp., 1977, 162\u2013170.","DOI":"10.1109\/SFCS.1977.6"},{"key":"12_CR20","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"Ch. H. Papadimitriou","year":"1976","unstructured":"Ch. H. Papadimitriou: The NP-completeness of the bandwidth minimization problem. Computing 16 (1976), 263\u2013270.","journal-title":"Computing"},{"key":"12_CR21","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1137\/0204038","volume":"4","author":"A. L. Rosenberg","year":"1975","unstructured":"A.L. Rosenberg: Preserving proximity in arrays. SIAM J. Comput. 4 (1975), 443\u2013460.","journal-title":"SIAM J. Comput."},{"key":"12_CR22","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF00288886","volume":"9","author":"A. L. Rosenberg","year":"1978","unstructured":"\u2014: Data encodings and their costs. Acta Inform. 9 (1978), 273\u2013292.","journal-title":"Acta Inform."},{"key":"12_CR23","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/322154.322160","volume":"26","author":"A. L. Rosenberg","year":"1979","unstructured":"\u2014: Encoding data structures in trees. J.ACM 26 (1979), 668\u2013689.","journal-title":"J.ACM"},{"key":"12_CR24","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF01776564","volume":"12","author":"A. L. Rosenberg","year":"1978","unstructured":"A.L. Rosenberg and L. Snyder: Bounds on the costs of data encodings. Math. Syst. Th. 12 (1978), 9\u201339.","journal-title":"Math. Syst. Th."},{"key":"12_CR25","unstructured":"\u2014: Perfect storage representations for families of data structures. In preparation, 1980."},{"key":"12_CR26","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF01744292","volume":"13","author":"A. L. Rosenberg","year":"1979","unstructured":"A.L. Rosenberg, D. Wood and Z. Galil: Storage representations for tree-like data structures. Math. Syst. Th. 13 (1979), 105\u2013130.","journal-title":"Math. Syst. Th."},{"key":"12_CR27","unstructured":"J.B. Saxe: Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. Carnegie-Mellon Tech. Rpt. CMU-CS-80-102, 1980."},{"key":"12_CR28","unstructured":"M. Sekanina: On an ordering of the set of vertices of a connected graph. Publ. Fac. Sci., Univ. Brno, No.412 (1960), 137\u2013142."},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"C.D. Thompson: Area-time complexity for VLSI. Proc. 11th ACM STOC Symp., 1979, 81\u201388.","DOI":"10.1145\/800135.804401"},{"key":"12_CR30","unstructured":"L.G. Valiant: Universality considerations in VLSI circuits. Unpublished typescript, 1979."}],"container-title":["Lecture Notes in Computer Science","Graphtheoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10291-4_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:11:05Z","timestamp":1742587865000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10291-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540102915","9783540384359"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-10291-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}