{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:38Z","timestamp":1787337578008,"version":"build-2736575974"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2002,1]]},"abstract":"<jats:p>\n                    We give improved approximations for two classical embedding problems: (i) minimizing the number of crossings in a drawing on the plane of a bounded degree graph; and (ii) minimizing the VLSI layout area of a graph of maximum degree four. These improved algorithms can be applied to improve a variety of VLSI layout problems. Our results are as follows. (i) We compute a drawing on the plane of a bounded degree graph in which the sum of the numbers of vertices and crossings is O(log\n                    <jats:sup>3<\/jats:sup>\n                    n )$ times the optimal minimum sum. This is a logarithmic factor improvement relative to the best known result. (ii) We compute a VLSI layout of a graph of maximum degree four in a square grid whose area is O(log\n                    <jats:sup>4<\/jats:sup>\n                    n )$ times the minimum layout area. This is an O(log\n                    <jats:sup>2<\/jats:sup>\n                    n ) improvement over the best known long-standing result.\n                  <\/jats:p>","DOI":"10.1137\/s0097539700373520","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"231-252","source":"Crossref","is-referenced-by-count":27,"title":["Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas"],"prefix":"10.1137","volume":"32","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90071-0"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796308217"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Sudipto Guha, Nested graph dissection and approximation algorithms, IEEE Comput. Soc. Press, Los Alamitos, CA, 2000, 126\u20131351931811","DOI":"10.1109\/SFCS.2000.892072"},{"key":"R4","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0604033"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Hillel Gazit, Gary Miller, Planar separators and the Euclidean norm, Lecture Notes in Comput. Sci., Vol. 450, Springer, Berlin, 1990, 338\u20133471081978","DOI":"10.1007\/3-540-52921-7_83"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson,\n                      Area\u2010efficient graph layouts (for VLSI)\n                      , in Proceedings of the 21st Annual IEEE Symposium on Foundations of Computer Science, Syracuse, NY, 1980, pp. 270\u2013281.","DOI":"10.1109\/SFCS.1980.13"},{"key":"R8","unstructured":"F. T. Leighton,\n                      Complexity Issues in VLSI\n                      , MIT Press, Cambridge, MA, 1983."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/s004539900039"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1049"},{"key":"R13","unstructured":"F. Shahrokhi, O. S\u00fdkora, L. Sz\u00e9kely, I. Vr\u0165o, Crossing numbers: bounds and applications, Bolyai Soc. Math. Stud., Vol. 6, J\u00e1nos Bolyai Math. Soc., Budapest, 1997, 179\u201320698k:05055"},{"key":"R14","unstructured":"J. D. Ullman,\n                      Computational Aspects of VLSI\n                      , Computer Science Press, Rockville, MD, 1984."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.6312176"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700373520","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:23Z","timestamp":1787336303000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700373520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["10.1137\/S0097539700373520"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700373520","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}