PQ-木を用いた平面グラフ埋込みアルゴリズムについて

千葉 則茂  西関 隆夫  阿部 茂信  小澤 孝夫  

誌名
電子情報通信学会論文誌 A   Vol.J67-A   No.2   pp.87-94
発行日: 1984/02/25
Online ISSN: 
DOI: 
Print ISSN: 0373-6091
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(604.4KB)>>
論文を購入




あらまし: 
与えられたグラフが平面グラフかどうか判定するばかりでなく,平面グラフを実際に平面に埋込むことが必要なことが多い.本文では与えられた平面グラフを線形時間で埋込む比較的単純なアルゴリズムを与える.BoothとLuekerはPQ木というデータ構造を用い,Lempel,Even,及びCederbaumにより与えられた“点付加アルゴリズム”と呼ばれる平面性判定アルゴリズムを線形時間アルゴリズムとして実現している.本文のアルゴリズムは彼等の判定アルゴリズムに基づいており,これまでに知られているHopcroftとTarjanによる“道付加アルゴリズム”と呼ばれる平面埋込みアルゴリズムと比較して概念的に簡単であり,理解しやすく,実現も容易である.