描画固定部分グラフを有するグラフにおける全域平面グラフの階層的抽出法

• Item type: SIG Technical Reports(1)
• 公開日: 2001-09-25
• タイトル: 描画固定部分グラフを有するグラフにおける全域平面グラフの階層的抽出法
• タイトル / 言語: en
• タイトル: Hierarchical Extraction of a Spanning Planar Subgraph under Fixed Embedding of Specified Subgraphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属: 広島大学大学院工学研究科情報工学専攻
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Hiroshima University
• 著者名: 姉ヶ山伸一郎; 高藤, 大介; 田岡, 智志; 渡邉, 敏正
• 著者名(英): Shinichiro, Anegayama; Daisuke, Takafuji; Satoshi, Taoka; Toshimasa, Watanabe
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では描画固定の部分グラフを含むグラフに対する全域平面最大部分グラフ抽出問題の発見的解法として，O(|V|^2)アルゴリズム plan_divide を提案する．描画が固定された部分グラフを含むグラフからの平面的グラフの抽出は応用上極めて有用である．plan_divide はこのような機能を持ち，かつ既存手法では処理不可能な大規模グラフ G = (V E)からの抽出を高速に行う．まず，|E| > max_edge なる G = (V E) を，辺数が max_edge 以下のいくつかのグラフG_iに分割した後，各G_iにおいて描画固定の部分グラフを含む全域平面的部分グラフを抽出し，このことと分割された部分グラフ間を接続する辺集合からの平面辺抽出に基づいてGの全域平面部分グラフを求める．但し，max_edgは既存手法で処理可能な辺数の上限を表わす．さらに，計算機による既存手法との比較実験を行い，plan_divide の性能を実験的に比較評価する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we present an O(|V|^2) heuristic algorithm plan_divide for hierarchically extracting a spanning subgraph under fixed embedding of some specified subgraphs. The purpose of plan_divide is to find a spanning planar subgraph of a huge given graph G = (V,E) having some subgraphs that requires fixed embedding. Let max_edge be the maximum cardinality of an edge set that existing planarization algorithm can deal with. First, plan_divide divides G with |E| > max_edge into some small graphs G_i = (V_i,E_i) with |E_i| <= max_edge for some i >= 1. Then plan_divide extracts a spanning planar subgraph of each G_i, and then finds planar edges from those connecting pairs of subgraphs G_i and G_j ( i \neq j). Furthermore, experimental results are given to compare plan_divide with other planarization algorithms, and to evaluate performance of plan_divide experimentally.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2001, 号 93(2001-AL-080), p. 1-8, 発行日 2001-09-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会