複数のグラフの同時平面描写について
スポンサーリンク
概要
- 論文の詳細を見る
グラフG=(V, E_1 ∪ E_2 ∪…∪ E_k) のある描写において, G_1=(V, E_1), G2=(V, E_2),…, G_k=(V, E_k) それぞれが平面描写になっているとき, このGの描写をG_1, G_2,…, G_kの同時平面描写といい, このようなGの描写が存在するとき, G_1, G_2,…, G_kは同時平面描写可能であるという. また, 上のようなGとG_1, G_2,…, G_kが与えられたとき, G_1, G_2,…, G_kが同時平面描写可能であるか否かを判定する問題をkグラフ同時平面性判定問題という. 本稿ではk=3のとき上の問題がNP完全であることを証明する.
- 社団法人電子情報通信学会の論文
- 1997-09-26
著者
関連論文
- D-1-2 グラフ描画アルゴリズムに基づいたデフォルメ路線図作成法(D-1. コンピュテーション, 情報・システム1)
- マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム
- 1-有界無競合ペトリネットにおける二つのトランジションの同時発火可能性を判定するYenのアルゴリズムの改良
- マークグラフにおけるトランジションの潜在的同時発火可能性判定アルゴリズム
- ペトリネットの部分クラスにおける同時発火可能性
- 定数幅量子ブランチングプログラムの計算能力 (計算理論とアルゴリズムの新展開)
- 妨害者のいる場合の最短経路問題
- 円筒上長方形交グラフの最大クリークを求めるアルゴリズム
- 妨害の下での最短経路問題
- パスグラフから区間グラフへの最小辺付加による変換の NP 完全性
- 交互シャフルについて
- 木上二重コンベックスグラフと二部サークルグラフの等価性
- 端子間に配線を通過させない順列配線のビア数最小化アルゴリズム
- 円筒上長方形交グラフの最大クリークを求めるアルゴリズム
- パスグラフから区間グラフへの最小辺付加による変換のNP完全性
- ある種のグラフにおける最大クリーク重みの折点数について
- 複数のグラフの同時平面描写について
- BD木を用いたマルチレイヤデータ管理構造の改良
- 平面グラフの最大重み窓問題
- 外窓上の頂点および辺の重みの和を最大にするような,2連結平面グラフの描写アルゴリズム
- パラメトリックグラフにおける最大クリ-ク重みの折れ点数
- あるグラフの極大頂点集合を表現するダイアグラム
- 階層的グラフの平面性判定アルゴリズム
- 2層配線における3端子ネットの分割
- 部品の端子間に配線を通過させない一層配線問題について
- 部品の反転を許さない一層平面配線問題について
- 類似検索手法LAESAの改良
- 引出し線を用いたラベル配置
- 引出し線を用いた地図ラベル配置アルゴリズム
- 引出し線を用いた地図ラベル配置アルゴリズム
- D-1-8 地図中の地点と線情報へのラベル配置のためのラベル候補作成法(D-1.コンピュテーション,一般講演)
- 地点の優先度を考慮した地図ラベル配置アルゴリズム
- グラフ描画へのラベル配置アルゴリズムの実験的評価
- グラフ描画へのラベル配置アルゴリズムの実験的評価
- D-1-1 優先度付き地図ラベル配置問題に対するラベル候補作成法(D-1. コンピュテーション, 情報・システム1)
- 辺がラベルをもつ無向グラフの描画法(グラフとネットワーク)
- D-1-2 辺がラベルをもつグラフの描画アルゴリズム
- グラフ描画における辺のラベルの配置法
- グラフ描画における辺のラベルの配置法
- D-1-10 引出し線を用いたラベル配置アルゴリズムの改良(D-1.コンピュテーション,一般講演)
- クラス編成問題に対する平等な割当決定法
- D-4-14 複数の参照点による距離近似を用いた類似検索手法の提案
- D-1-11 図形データの重なり判定を高速化するデータ構造の提案(D-1.コンピュテーション,一般講演)
- D-1-9 二次元点パターンマッチング問題に対する高速なアルゴリズム(D-1.コンピュテーション,一般講演)
- 地理データに対する領域隣接グラフを利用した領域管理手法(研究速報)
- TLAESAに基づく近似κ近傍検索手法(研究速報)
- 最大重みクリークを効率良く抽出するための頂点系列の生成法
- 類似データ検索のためのデータ構造とアルゴリズム
- D-4-9 類似検索手法TLAESAの改良(D-4. データ工学, 情報・システム1)
- D-4-8 地理データに対する領域管理手法の実験的評価(D-4. データ工学, 情報・システム1)
- D-1-3 頂点がグループ分けされた階層的グラフの描画法(D-1. コンピュテーション, 情報・システム1)
- Comparability supergraphを用いた最大重みクリーク問題の厳密解法
- Chordal SupergraphとChordal Subgraphによる最大クリーク問題の緩和問題構成法について
- A-34 グラフ最適化問題に対する緩和問題の構成法の提案(最適化,A.アルゴリズム・基礎)
- D-1-3 グラフの最大独立頂点集合数の上界の計算法の提案
- グラフ描画における頂点ラベルの配置法
- 類似検索手法による無向グラフの最短経路探索法
- 回線交換網の経路設定に関する研究
- ゲーム理論を用いたパケット網経路制御法
- GBD木における線分の分割法の改良
- GBD木における線分の分割法の改良
- 2種類の理想距離によるEadesのグラフ描画法の改良
- グラフ描画における頂点ラベルの配置法
- 容量制限付きk-center問題の近似解法の実験的評価