内部3連結グラフの格子凸描画

摘要

平面グラフの全ての点を整数格子点上に配置し，全ての辺を互いに交わることのない直線分で描画 し，外面を含む全ての面を凸多角形であるようにしたい．そのような描画を格子凸描画と呼ぶ．平面グラフGが凸描画できるための必要十分条件は，Cが内部3連結であることである．内部3連結平面グラフCの3連結成分分解木T（G）に葉がたかだか3枚しかないとき，大きさ（n-1）×（n-1）の整数格子内に線形時間で格子凸描画できることが知られている・ここで，m はGの点数である．またT（G）に葉がちょうど4枚しかないとき，Gを大きさ2n×4nの整数格子内に線形時間で格子凸描画できることが知られている．本論文は，この格子凸描画の大きさ2n × 4nを2n×2nに改良する・すなわち，内部3連結平面グラフGの分解木T（G）に葉がちょうど4枚あるとき，Gを2n×2nの大きさの整数格子内に線形時間で格子凸描画するアルゴリズムを与える．