多面体グラフ
多面体グラフが立方体グラフならば、その立方体グラフは、多面体の次元と各頂点の次数が一致する多面体(simple polytedron)のグラフである。多面体グラフが最大平面グラフ(辺を加えることで平面グラフではなくなるグラフ)ならば、多面体グラフが単体に対応する多面体グラフである。また、木のすべての葉を接続する閉路を外側に追加することによって生成されるHalinグラフは、多面体グラフの別の重要な概念となる。
多面体グラフ(ためんたいグラフ)は凸多面体の頂点と辺からなる無向グラフであり、純粋なグラフ理論的には、多面体グラフは3-頂点連結グラフである平面グラフである。