@techreport{oai:ipsj.ixsq.nii.ac.jp:00032018,
 author = {姉ヶ山伸一郎 and 高藤, 大介 and 田岡, 智志 and 渡邉, 敏正 and Shinichiro, Anegayama and Daisuke, Takafuji and Satoshi, Taoka and Toshimasa, Watanabe},
 issue = {93(2001-AL-080)},
 month = {Sep},
 note = {本稿では描画固定の部分グラフを含むグラフに対する全域平面最大部分グラフ抽出問題の発見的解法として，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 の性能を実験的に比較評価する．, 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.},
 title = {描画固定部分グラフを有するグラフにおける全域平面グラフの階層的抽出法},
 year = {2001}
}