グラフの最小線分数による直交線分描画

• Item type: SIG Technical Reports(1)
• 公開日: 1988-05-23
• タイトル: グラフの最小線分数による直交線分描画
• タイトル / 言語: en
• タイトル: RECTILINEAR DRAWING OF A GRAPH ON A PLANE WITH THE MINIMUM NUMBER OF SEGMENTS
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学工学部電気電子工学科
• 著者所属: 東京工業大学工学部電気電子工学科
• 著者所属(英): en
• 著者所属(英): Dept. of E. E. Engineering, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Dept. of E. E. Engineering, Tokyo Institute of Technology
• 著者名: 梶谷, 洋司; 高橋, 俊彦
• 著者名(英): Y., Kajitani; T., Takahasi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面上に点の位置が固定されて表現されているグラフGをリベテッドグラフと言う。Gをその平面上で、各枝を水平および垂直な線分のみで描いた図形を直交線分描画と呼ぶ。どの点の次数も4以下で同じ位置を占める2点が存在しないリベテッドグラフは常に直交線分描画をもつ。与えられたリベテッドグラフGに対し、その直交線分描画には多様性があるが、本文では線分数の最小化を問題としている。主要な成果として、点の位置が一般である場合、任意のりベテッドグラフGを3m（m：枝数）以下の線分数で描画する時間O(m)のアルゴリズムを与えている。更に、4レギュラーなバイパータイトリベテッドグラフと呼ばれるグラフは実際に3mだけの線分数を要することを証明している。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A rivetted graph G(V,E) is a graph hose vertices are fixed on a plane in position. Its rectilinear drawing D(G) is a configuration of G on the plane in such a way that each edge is composed of horizontal and vertical segments. This paper concerns with reduction of the number of segments. as a main result, it is proved by presenting a linear time and space construction algorithm that any graph has a rectilinear drawing such that the total number of segments is no more than 3｜E｜. It is shown that the 4-regural bipartite graph needs this number of segment.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1988, 号 36(1988-AL-001), p. 1-8, 発行日 1988-05-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会