{"created":"2023-07-27T06:26:19.620765+00:00","id":9997,"links":{},"metadata":{"_buckets":{"deposit":"44d96bf1-9cd2-4d99-aa5f-c04626fe75a0"},"_deposit":{"created_by":3,"id":"9997","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"9997"},"status":"published"},"_oai":{"id":"oai:kanazawa-u.repo.nii.ac.jp:00009997","sets":["934:935:936"]},"author_link":["614"],"item_8_biblio_info_8":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2009-01-01","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"2941","bibliographicPageStart":"2938","bibliographicVolumeNumber":"2009","bibliographic_titles":[{"bibliographic_title":"Proceedings - IEEE International Symposium on Circuits and Systems"}]}]},"item_8_description_21":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"We study the problem of embedding a guest graph into an optimally-sized grid with minimum edge-congestion. Based on a wellknown notion of graph separator, we prove that any guest graph can be embedded with a smaller edge-congestion as the guest graph has a smaller separator, and as the host grid has a higher dimension. Our results imply the following: An N-node planar graph with maximum node degree Δ can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ2 logN) if d = 2, O(Δ2 log logN) if d = 3, and O(Δ2) otherwise. An N-node graph with maximum node degree Δ and a treewidth O(1), such as a tree, an outerplanar graph, and a series-parallel graph, can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Δ) for d ≥ 2.","subitem_description_type":"Abstract"}]},"item_8_description_5":{"attribute_name":"提供者所属","attribute_value_mlt":[{"subitem_description":"金沢大学理工研究域電子情報学系","subitem_description_type":"Other"}]},"item_8_publisher_17":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"IEEE = Institute of Electrical and Electronics Engineers"}]},"item_8_version_type_25":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Matsubayashi, Akira"}],"nameIdentifiers":[{},{},{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-10-03"}],"displaytype":"detail","filename":"TE-PR-MATSUBAYASHI-A-2938.pdf","filesize":[{"value":"1.3 MB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"TE-PR-MATSUBAYASHI-A-2938.pdf","url":"https://kanazawa-u.repo.nii.ac.jp/record/9997/files/TE-PR-MATSUBAYASHI-A-2938.pdf"},"version_id":"3466daa2-80aa-401f-a888-da72b055fe30"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"conference paper","resourceuri":"http://purl.org/coar/resource_type/c_5794"}]},"item_title":"Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion"}]},"item_type_id":"8","owner":"3","path":["936"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-10-03"},"publish_date":"2017-10-03","publish_status":"0","recid":"9997","relation_version_is_last":true,"title":["Separator-Based Graph Embedding into Higher-Dimensional Grids with Small Congestion"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2023-07-28T01:45:16.857259+00:00"}