一般化ドーナツグラフの格子直線描画

添田 知宏  三浦 一之  

誌名
電子情報通信学会論文誌 D   Vol.J101-D   No.3   pp.494-501
発行日: 2018/03/01
Online ISSN: 1881-0225
DOI: 10.14923/transinfj.2017PDP0001
論文種別: 特集論文 (学生論文特集)
専門分野: 情報・システム基礎
キーワード: 
グラフ描画,  格子直線描画,  平面グラフ,  ドーナツグラフ,  

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


あらまし: 
平面グラフGの各点が整数格子の格子点上に配置され,Gの各辺が互いに交差しない直線分として描かれる描画をGの格子直線描画という.任意の平面グラフGは(n-2)×(n-2)の大きさの整数格子内に格子直線描画できることが知られている [15].ここでnGの点数である.一方,入力グラフにある種の制約があるならば,より小さな面積の格子内に格子直線描画できることが予想される.本論文では,まず5連結p-k重ドーナツグラフGの定義を与える.更に,5連結p-k重ドーナツグラフGは,n/(2k-2)+(2k-5) × (2k-1),すなわちO(n)の面積の整数格子内に格子直線描画かつ格子凸描画できることを示すとともに,そのような描画を求める線形時間アルゴリズムを与える.また,5連結p-k重ドーナツグラフを4連結(3連結)に拡張した,4連結(3連結)p-k重ドーナツグラフGの定義を与える.更に,4連結(3連結)p-k重ドーナツグラフGは,n/(2k-2)+(2k-5) × (2k-1) の面積の整数格子内に格子直線描画できることを示すとともに,そのような描画を求める線形時間アルゴリズムを与える.