平面グラフの正規分割,リアライザ,Schnyderラベル付けおよび外三角凸描画

摘要

平面グラフの正規分割,リアライザおよびSchnyderラベル付けという3つの概念は,平面グラフの直線描画や凸描画で重要な役割を果たしている。 平面グラフGが3連結であることは,Gにそれらが存在するための十分条件であることは知られていたが,必要十分条件は知られていなかった。 本論文ではそれらが存在するための必要十分条件を与えるとともに,正規分割,リアライザ,Schnyderラベル付け,外三角凸描画の4つの概念が互いに同値であることを示す。