{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T17:41:11Z","timestamp":1697910071023},"reference-count":14,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":7749,"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":[[1986,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An important problem in the design of a VLSI chip is that of determining how much area is taken to embed a graph G into a planar grid when the VLSI chip is modeled using a graph called a planar grid and a circuit is expressed by a graph G representing wiring connections between elements. Discussed for various graphs will be the upper and lower bounds on the planar grid area into which a graph is embedded. In this paper we consider the problem of embedding a <jats:italic>d<\/jats:italic>\u2010way shuffle graph into a planar grid, using a model which has been extended so that a graph with degree five or more can be embedded. <jats:italic>d<\/jats:italic>\u2010way shuffle graphs are also of theoretical interest since data exchange can be done in high speed like a shuffle exchange graph and a CCC. By using a relationship between the number of crossings of a graph and its area, we show that for the infinite number of <jats:italic>d<\/jats:italic> and <jats:italic>k<\/jats:italic> an area proportional to <jats:italic>dk+1\/k)<\/jats:italic><jats:sup>2<\/jats:sup> is required to embed a <jats:italic>dk<\/jats:italic>\u2010vertex, <jats:italic>d<\/jats:italic>\u2010way shuffle graph. Using this result, the previous lower bound of the area can be improved. Further, for an embedding of a graph G we present an embedding method of G which uses a graph with a known embedding area. By using this result we show that if <jats:italic>d<\/jats:italic> is a power of 2, a <jats:italic>dk<\/jats:italic>\u2010vertex, <jats:italic>d<\/jats:italic>\u2010way shuffle graph can be embedded in an area proportional to (<jats:italic>dk<\/jats:italic>+1\/2)<jats:sup>2<\/jats:sup>.<\/jats:p>","DOI":"10.1002\/scj.4690170602","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T12:03:35Z","timestamp":1183809815000},"page":"10-19","source":"Crossref","is-referenced-by-count":0,"title":["Embedding area of d\u2010way shuffle graph on a VLSI model"],"prefix":"10.1002","volume":"17","author":[{"given":"Koichi","family":"Wada","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ken'Ichi","family":"Hagihara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Nobuki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"family":"Tokura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/62.322423"},{"key":"e_1_2_1_3_2","volume-title":"On linear area embedding of planar graph, STANCS\u201081\u2013876","author":"Doley D.","year":"1981"},{"key":"e_1_2_1_4_2","first-page":"12","article-title":"An investigation on an embedding of a graph into a three\u2010dimensional grid space","volume":"66","author":"Hagihara","year":"1983","journal-title":"Trans. I.E.C.E. (D)"},{"key":"e_1_2_1_5_2","first-page":"7","article-title":"On relations between the area required for an embedding of a graph and the number of crossings","volume":"66","author":"Kimoto","year":"1983","journal-title":"Trans. I.E.C.E. (D)"},{"key":"e_1_2_1_6_2","volume-title":"Complexity issues in VLSI","author":"Leighton F. T.","year":"1983"},{"key":"e_1_2_1_7_2","volume-title":"Area\u2010efficient graph layouts (for FLSI), CMU\u2010CS\u201080\u2013138","author":"Leiserson C. E.","year":"1980"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"F. P.PreparataandJ.Vuillemin. The cube\u2010connected\u2010cycles: A versatile network for parallel computation (Extended abstract) I.E.E.E. 20th Ann. Symp. FOCS pp.140\u2013147(Oct. 1979).","DOI":"10.1109\/SFCS.1979.43"},{"key":"e_1_2_1_9_2","volume-title":"Three\u2010dimensional VLSI 1: A case study, RC8745","author":"Rosenberg A. I.","year":"1981"},{"key":"e_1_2_1_10_2","first-page":"6","article-title":"On the area\u2010time\u2010complexity of a cyclic shift","volume":"66","author":"Setani","year":"1983","journal-title":"Trans. I.E.C.E. (D)"},{"key":"e_1_2_1_11_2","first-page":"7","article-title":"An embedding of a graph in VLSI model","volume":"65","author":"Suzuki","year":"1982","journal-title":"Trans. I.E.C.E. (D)"},{"key":"e_1_2_1_12_2","first-page":"5","article-title":"On an embedding of a graph into a VLSI model","volume":"67","author":"Toda","year":"1984","journal-title":"Trans. I.E.C.E. (D)"},{"key":"e_1_2_1_13_2","first-page":"2","article-title":"Universality consideration in VLSI circuits","volume":"30","author":"Valiant L. G.","year":"1980","journal-title":"I.E.E.E. Trans. Comput."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"L. G.ValiantandG. J.Brebner. Universal schemes for parallel processing Proc. of ACM 13th Ann. STOC pp.263\u2013277(May 1981).","DOI":"10.1145\/800076.802479"},{"key":"e_1_2_1_15_2","first-page":"8","article-title":"On the area of a logical circuit on VLSI","volume":"65","author":"Yasuura","year":"1982","journal-title":"Trans. I.E.C.E. (D)"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690170602","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690170602","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T16:59:42Z","timestamp":1697821182000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690170602"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1]]},"references-count":14,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1986,1]]}},"alternative-id":["10.1002\/scj.4690170602"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690170602","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,1]]}}}