{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:31:12Z","timestamp":1750307472459,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>Interconnect dominated electronic design stimulates a demand for developing circuits on the third dimension, leading to 3-D integration. Recent advances in chip fabrication technology enable 3-D circuit manufacturing. However, there is still a possible barrier of design complexity in exploiting 3-D technologies. This article discusses the impact of migrating from 2-D to 3-D on the difficulty of floorplanning and placement. By looking at a basic formulation of the graph cuboidal dual problem, we show that the 3-D cases and the 3-layer 2.5-D cases are fundamentally more difficult than the 2-D cases in terms of computational complexity. By comparison among these cases, the intrinsic complexity in 3-D floorplan structures is revealed in the hard-to-decide relations between topological connections and geometrical contacts. The results show possible challenges in the future for physical design and CAD of 3-D integrated circuits.<\/jats:p>","DOI":"10.1145\/1835420.1835426","type":"journal-article","created":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T15:38:13Z","timestamp":1286897893000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Complexity of 3-D floorplans by analysis of graph cuboidal dual hardness"],"prefix":"10.1145","volume":"15","author":[{"given":"Renshen","family":"Wang","sequence":"first","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangeline","family":"Young","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shatin N.T. Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chung-Kuan","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of California, San Diego, La Jolla, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,10,7]]},"reference":[{"volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference, 108--114","author":"Bhasker J.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90004-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Design. 211--217","author":"Deng Y.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278637"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.920580"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(95)00257-X"},{"volume-title":"Complexity of Computer Computations.","author":"Karp R. M.","key":"e_1_2_1_8_1"},{"volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference. 655--656","author":"Kozminski K.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDT.2005.149"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320191"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Design. 501--504","author":"Wu G.-M.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","unstructured":"}}Yamazaki H. Sakanushi K. Nakatake S. and Kajitani Y. 2000. The 3D-packing by meta data structure and packing heuristics. IEICE Trans. Fundamentals 639--645.  }}Yamazaki H. Sakanushi K. Nakatake S. and Kajitani Y. 2000. The 3D-packing by meta data structure and packing heuristics. IEICE Trans. Fundamentals 639--645."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1233501.1233666"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1835420.1835426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1835420.1835426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:08:45Z","timestamp":1750248525000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1835420.1835426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1145\/1835420.1835426"],"URL":"https:\/\/doi.org\/10.1145\/1835420.1835426","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2010,9]]},"assertion":[{"value":"2009-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-10-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}