凸部分グラフ

計量グラフ理論では、無向グラフGの凸部分グラフは、 G内の2 つの頂点間の最短経路をすべて含む部分グラフです。したがって、これは幾何学における凸集合の定義に類似しており、凸集合は、その集合に含まれるすべての点のペア間の線分を含みます。

凸部分グラフは、部分立方体とメジアングラフの理論において重要な役割を果たします。特に、メジアングラフでは、凸部分グラフはHelly プロパティを持ちます。つまり、凸部分グラフの族が、すべてのペアワイズ交差が空でないというプロパティを持つ場合、族全体に空でない交差が存在します。

• Bandelt, H.-J.; Chepoi, V. (2008)、「メトリック グラフ理論と幾何学: 概観」、Goodman, JE ; Pach, J. ; Pollack, R. (編)、離散幾何学と計算幾何学に関する概観: 20 年後(PDF)、Contemporary Mathematics、第 453 巻、プロビデンス、RI: AMS、pp. 49–86。
• イムリッチ、ウィルフリード、クラヴジャー、サンディ（1998）、「二部グラフの凸性補題と展開手順」、ヨーロッパ組合せ論ジャーナル、19（6）：677–686、doi：10.1006/eujc.1998.0229、MR  1642702。