平面三角格子上におけるベンド数の少ないグラフ描画
スポンサーリンク
概要
- 論文の詳細を見る
平面格子上に最大次数4以下の平面連結グラフを,ベンド数(Bend Number=曲がり数)が最小となるように描画する問題は多くの研究がなされ,解決されている.なお,格子上への描画はグラフの直交描画とよばれている.しかし,対象となるグラフは最大次数が4以下のものに限定される.ここでは平面上の三角格子を利用して,この上に最大次数6以下の平面グラフをベンド数が少ない,できれば最小となる描画を試みた.グラフ直交描画の手法を踏襲し,ベンド数が最小ではないが上限と下限の評価できるアルゴリズムを提案する.またアルゴリズムを実装し,小さいグラフについては実際に描画を行った.直交描画では生じない三角格子上での固有の難しい問題があり,最終的な解決には至っていない.今後の研究が望まれる.
- 一般社団法人情報処理学会の論文
- 2008-01-18
著者
関連論文
- 平面格子上の2種点集合の平衡分割問題
- 木をアクセス構造とする多画像視覚型秘密分散法
- サイクルをアクセス構造にもつ多画像視覚型秘密分散法
- 二面体群をアクセス構造に持つ多画像視覚型秘密分散法
- 平面上の2種点集合の平衡分割(セッション1)
- 平面上の3角格子と離散構造問題 (情報学シンポジウム特集号)
- Visual card games for boys and girls (ワイドバンドシステム・情報通信基礎サブソサイエティ合同研究会)
- Visual card games for boys and girls (情報セキュリティ・情報通信基礎サブソサイエティ合同研究会)
- Visual card games for boys and girls (情報理論・情報通信基礎サブソサイエティ合同研究会)
- 茨大型ライフゲーム
- 茨大型ライフゲーム(数理モデルの組合せ論的構造)
- 階層構造をもった暗号化ファイルシステムについて
- 階層構造をもった暗号化ファイルシステムについて
- 階層構造をもった暗号化ファイルシステムについて
- 階層構造をもった暗号化ファイルシステムについて
- 平面三角格子上におけるベンド数の少ないグラフ描画
- 幾何的交互道被覆と多項式時間アルゴリズム
- Complete Bipartite Geometric Graphs and Alternating Paths (情報学シンポジウム特集号)
- 平面上の点集合の平衡分割問題
- グラフの平面への直線埋込み問題
- 管理機能付き公開鍵暗号システム
- 管理機能付き公開鍵暗号システム
- 管理機能付き公開鍵暗号システム
- 管理機能付き公開鍵暗号システム
- 2つのグループのための視覚型カードゲーム(情報通信基礎サブソサイエティ合同研究会)
- 2つのグループのための視覚型カードゲーム(情報通信基礎サブソサイエティ合同研究会)
- 2つのグループのための視覚型カードゲーム(情報通信基礎サブソサイエティ合同研究会)
- 離散・計算幾何学国際会議(JCDCG) : 15年のあゆみ (前原濶教授退職記念号)