{"created":"2021-03-01T06:06:45.750658+00:00","id":3019,"links":{},"metadata":{"_buckets":{"deposit":"55a2b77a-ced1-4b8c-a1d8-156fb58a3fb2"},"_deposit":{"id":"3019","owners":[],"pid":{"revision_id":0,"type":"depid","value":"3019"},"status":"published"},"_oai":{"id":"oai:niigata-u.repo.nii.ac.jp:00003019","sets":["423:424:425","453:454"]},"item_5_alternative_title_1":{"attribute_name":"その他のタイトル","attribute_value_mlt":[{"subitem_alternative_title":"On Heights of Straight Line Drawings of Plane Graphs"}]},"item_5_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"1993-09","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"9","bibliographicPageEnd":"1858","bibliographicPageStart":"1853","bibliographicVolumeNumber":"34","bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"},{"bibliographic_title":"情報処理学会論文誌","bibliographic_titleLang":"en"}]}]},"item_5_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"グラフの各枝を互いに交差しない曲線によって平面に描いた図形を平面グラフと呼ぶ．平面グラフの各枝がすべて直線分によって描かれているとき，特にこれを直線分描画と呼ぶ．計算機で直線分描画を処理したり，ディスプレイに出力する場合は，描画されたグラフの点には整数値のxy座標が与えられる．このような直線分描画は格子上にある，あるいは格子上の直線分描画であるという．格子上の直線分描画に関する問題の一つに，「任意のn点の平面グラフを格子上の直線分描画するために十分な領域はどのくらいか」というものがある．この問いに対する答えとして，現在までの最良の結果は「任意のn点の平面グラフは幅n-2，高さn-2の領域内で格子上に直線分描画できる」というものであるが，これらの値が必要十分であるかどうかはわかっていない．筆者はこうした結果を踏まえ，高さ（もしくは幅）のみについてであれば，必要十分な値を求められる-任意のn点の平面グラフを格子上に直線分描画するために必要十分な高さは⌈(2n-4)/3⌉-と予想する．本文では，この予想を裏付ける結果として，任意のn点の平面グラフGは，点のy座標のうち互いに異なるものが高々⌈(2n-1)/3⌉個であるような直線分描画G^*を持つことを構成的に示す．","subitem_description_type":"Abstract"},{"subitem_description":"Let G^* be a straight line drawing of a plane graph in the xy-plane. The number of y-coordinates (of vertices) d(G^*) is the number of vertices with pairwise distinct y-coordinates in G^*. d(G^*) is a parameter which is closely related to the height of straight line drawing of a graph on a grid. We show that any plane with n vertices has a drawing which satisfies d(G^*) ≤⌈(2n-1)/3⌉ and present a constructive algorithm which obtains such a straight line drawing.","subitem_description_type":"Abstract"}]},"item_5_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"40435","nameIdentifierScheme":"WEKO"}],"names":[{"name":"Takahashi, Toshihiko"}]}]},"item_5_publisher_7":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会"}]},"item_5_select_19":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_select_item":"publisher"}]},"item_5_source_id_11":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_5_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"03875806","subitem_source_identifier_type":"ISSN"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"高橋, 俊彦"}],"nameIdentifiers":[{"nameIdentifier":"40434","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-07-30"}],"displaytype":"detail","filename":"34(9)_1853-1858.pdf","filesize":[{"value":"510.5 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"34(9)_1853-1858.pdf","url":"https://niigata-u.repo.nii.ac.jp/record/3019/files/34(9)_1853-1858.pdf"},"version_id":"ad766a84-c7dc-49b2-bc25-a33f5c73e547"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"平面グラフの直線分描画の高さについて","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"平面グラフの直線分描画の高さについて"},{"subitem_title":"平面グラフの直線分描画の高さについて","subitem_title_language":"en"}]},"item_type_id":"5","owner":"1","path":["454","425"],"pubdate":{"attribute_name":"公開日","attribute_value":"2009-07-15"},"publish_date":"2009-07-15","publish_status":"0","recid":"3019","relation_version_is_last":true,"title":["平面グラフの直線分描画の高さについて"],"weko_creator_id":"1","weko_shared_id":null},"updated":"2022-12-15T03:36:12.843997+00:00"}