抄録
A-003
グラフのn多角形上描画可能性判定アルゴリズムについて
◎平澤 紹・宮田洋行・中野眞一（群馬大）
さまざまな基準でグラフをより理解しやすく描画する研究が盛んになされている。例えば、外平面的グラフは円周上に頂点を配置し全ての辺を交差無く直線で描画できることが知られている。本研究ではさらに、外平面的グラフを出来る限り小さいnについてn多角形の辺上に各頂点を配置し描画することを考える。そして、与えられたグラフがn多角形上に描画可能かO(V) (V:グラフの頂点数)時間で判定するアルゴリズムを提案する。
