平面性判定:完全二部グラフ K2,5 の例 Graph : 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0-th block with vertices 0 1 2 3 4 5 6 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 Current picture : 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 2 1 3 0 R[1] : 0 3 1 2 0 Extending path in R[0] : 0 4 1 Current picture : 0 0 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 4 1 3 0 R[1] : 0 3 1 2 0 R[2] : 0 2 1 4 0 Extending path in R[0] : 0 5 1 Current picture : 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 5 1 3 0 R[1] : 0 3 1 2 0 R[2] : 0 2 1 4 0 R[3] : 0 4 1 5 0 Extending path in R[0] : 0 6 1 Current picture : 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 Regions : R[0] : 0 6 1 3 0 R[1] : 0 3 1 2 0 R[2] : 0 2 1 4 0 R[3] : 0 4 1 5 0 R[4] : 0 5 1 6 0 G is planar.