面について独立な頂点配置を条件とする平面グラフ埋込み
スポンサーリンク
概要
- 論文の詳細を見る
この論文では,2連結平面グラフG=(V,E)(V,EはそれぞれGの頂点集合と辺集合)とVの部分集合Uが与えられたとき,「Gのどの面周上にもUの頂点はたかだか1個しか現れないというようなGの平面への埋込みが可能かどうか,可能ならそのような平面埋込みの一つを求めよ」という問題を解いている.解法は,グラフの平面性判定に用いられる点付加アルゴリズムに基づいており,そのインプルメンテーションにPQ-木とよばれるデータ構造を用いている.グラフに分離成分が存在するために数多くの平面埋込みが存在する場合,問題の条件を満たすような埋込みを能率良く求めるための戦略と,それをPQ-木において実行するための具体的な方策を示している.
- 社団法人電子情報通信学会の論文
- 1993-03-25
著者
関連論文
- 配水管網内の水質計算のためのアルゴリズムとデータ構造
- 手話辞典のイラスト付手話説明文からの3次元手話アニメーション自動生成
- 手話辞典のイラスト付手話説明文からの3次元手話アニメーション自動生成
- イラスト付手話説明文からの3D手話アニメーション自動生成
- 流出量の圧力依存性を考慮した配水管網の定常流解析
- 移動視点からの多角形可視部分計算
- D-12-43 日本語手話説明文からの手動作認識と合成
- 2グラフの最遠共通木対とその能動回路区間解析への応用(グラフ,ネットワークとアルゴリズムおよび一般)
- 能動回路の区間解析と2-グラフの最遠共通木対
- 面について独立な頂点配置を条件とする平面グラフ埋込み