{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T04:59:03Z","timestamp":1698037143145},"reference-count":7,"publisher":"Wiley","issue":"10","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":6653,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1989,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In designing VLSI, the problem of how large the chip area will be is of considerable interest. Thus, the primary objective in investigating this problem is to consider formally processing elements and wires of a circuit to be vertices and edges of an undirected graph, and then clarify the area sufficient or necessary to embed this graph onto a rectangular grid graph according to a certain embedding method (this is called an embedding model). In this paper, vertices correspond to a rectangular graph such that [length of long side]\/[length of short side] \u2264 constant. It is shown that under an embedding model, which forbids images of edges (wires) from passing through the inside of the vertex region of the rectangle, the maximum lower bound of the area corresponding to a general <jats:italic>n<\/jats:italic>\u2010vertex <jats:italic>d<\/jats:italic>\u2010degree graph is \u03c9<jats:italic>d<\/jats:italic><jats:sub>2<\/jats:sub><jats:italic>n<\/jats:italic><jats:sub>2<\/jats:sub>. As the result, it is seen that the conventionally known upper bound <jats:italic>O<\/jats:italic>(<jats:italic>d<jats:sup>2<\/jats:sup>n<jats:sup>2<\/jats:sup><\/jats:italic>) cannot be improved any further as long as all <jats:italic>n<\/jats:italic>\u2010vertex <jats:italic>d<\/jats:italic>\u2010degree graphs are considered.<\/jats:p>","DOI":"10.1002\/scj.4690201004","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T16:50:37Z","timestamp":1183827037000},"page":"39-52","source":"Crossref","is-referenced-by-count":0,"title":["Maximum lower bound on embedding areas of general graphs"],"prefix":"10.1002","volume":"20","author":[{"given":"Koichi","family":"Wada","sequence":"first","affiliation":[]},{"given":"Kimio","family":"Kawaguchi","sequence":"additional","affiliation":[]},{"given":"Hideyuki","family":"Fujishima","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"C. D.Thompson.A complexity theory for VLSI. Technical Report CMU\u2010CS\u201080\u2010140 Dept. of Computer Science Carnegie\u2010Mellon University Pittsburgh PA pp.51\u201360(Aug.1980)."},{"key":"e_1_2_1_3_2","first-page":"80","volume-title":"Computational aspects of VLSI","author":"Ullman J. D.","year":"1984"},{"issue":"7","key":"e_1_2_1_4_2","first-page":"898","article-title":"Embedding of graphs in VLSI model","volume":"65","author":"Suzuki Hagiwara","year":"1982","journal-title":"Journal of Society for Signal Processing (D)"},{"issue":"5","key":"e_1_2_1_5_2","first-page":"1011","article-title":"On embedding areas of d\u2010degree shuffle graphs in VLSI","volume":"68","author":"Wada Hagiwara","year":"1985","journal-title":"Journal of Society for Signal Processing (D)"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206022"},{"key":"e_1_2_1_7_2","unstructured":"M.Snir.Lower bounds on VLSI implementations of communication networks. Technical Report 32 Courant Institute of Mathematical Sciences New York University New York (May1981)."},{"key":"e_1_2_1_8_2","first-page":"286","volume-title":"Theory of Graphs and Networks","author":"Ozaki","year":"1973"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690201004","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690201004","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T13:40:32Z","timestamp":1697982032000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690201004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,1]]},"references-count":7,"journal-issue":{"issue":"10","published-print":{"date-parts":[[1989,1]]}},"alternative-id":["10.1002\/scj.4690201004"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690201004","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,1]]}}}