端子頂点グラフの全域平面部分グラフ抽出法に対する切断対とネット描画変更に基づく高精度化

摘要

本稿の主題は，電気回路のグラフモデルである端子頂点グラフに対する最大全域平面部分グラフ抽出問題である．本問題はNP－困難であり，既に何種類かの発見的解法が提案されている．その中で、ネットのグラフ表現変更により平面辺を抽出する手法の解精度が良いことが知られている．本稿では，切断点に加えてより多くの切断対に着目してネットのグラフ表現を変更する手法を提案し，その性能を計算機実験により既存手法と比較評価する．