平面性判定：正二十面体グラフの例 Graph : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0-th block with vertices 0 1 2 3 4 5 6 7 8 9 10 11 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 Current picture : 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 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 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 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 1 2 0 R[1] : 0 2 1 0 Extending path in R[0] : 0 8 1 Current picture : 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 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 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 0 0 0 0 0 0 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 8 1 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 Extending path in R[0] : 0 3 8 Current picture : 0 1 1 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 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 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 1 1 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 3 8 1 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 Extending path in R[0] : 0 7 2 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 8 1 2 7 0 Extending path in R[4] : 1 6 2 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 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 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 8 1 6 2 7 0 R[5] : 1 2 6 1 Extending path in R[4] : 1 4 6 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 8 1 4 6 2 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 Extending path in R[4] : 3 10 5 2 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 10 5 2 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 8 1 4 6 2 5 10 3 Extending path in R[4] : 3 7 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 8 1 4 6 2 5 10 3 R[8] : 3 10 5 2 7 3 Extending path in R[7] : 3 11 4 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 6 2 5 10 3 R[8] : 3 10 5 2 7 3 R[9] : 3 8 1 4 11 3 Extending path in R[9] : 8 4 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 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 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 6 2 5 10 3 R[8] : 3 10 5 2 7 3 R[9] : 3 8 4 11 3 R[10] : 8 1 4 8 Extending path in R[7] : 4 9 5 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 9 5 10 3 R[8] : 3 10 5 2 7 3 R[9] : 3 8 4 11 3 R[10] : 8 1 4 8 R[11] : 4 6 2 5 9 4 Extending path in R[11] : 6 5 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 9 5 10 3 R[8] : 3 10 5 2 7 3 R[9] : 3 8 4 11 3 R[10] : 8 1 4 8 R[11] : 4 6 5 9 4 R[12] : 6 2 5 6 Extending path in R[8] : 5 7 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 9 5 10 3 R[8] : 3 10 5 7 3 R[9] : 3 8 4 11 3 R[10] : 8 1 4 8 R[11] : 4 6 5 9 4 R[12] : 6 2 5 6 R[13] : 5 2 7 5 Extending path in R[11] : 6 9 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 9 5 10 3 R[8] : 3 10 5 7 3 R[9] : 3 8 4 11 3 R[10] : 8 1 4 8 R[11] : 4 6 9 4 R[12] : 6 2 5 6 R[13] : 5 2 7 5 R[14] : 6 5 9 6 Extending path in R[8] : 10 7 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 9 5 10 3 R[8] : 3 10 7 3 R[9] : 3 8 4 11 3 R[10] : 8 1 4 8 R[11] : 4 6 9 4 R[12] : 6 2 5 6 R[13] : 5 2 7 5 R[14] : 6 5 9 6 R[15] : 10 5 7 10 Extending path in R[9] : 8 11 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 9 5 10 3 R[8] : 3 10 7 3 R[9] : 3 8 11 3 R[10] : 8 1 4 8 R[11] : 4 6 9 4 R[12] : 6 2 5 6 R[13] : 5 2 7 5 R[14] : 6 5 9 6 R[15] : 10 5 7 10 R[16] : 8 4 11 8 Extending path in R[7] : 9 10 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 4 9 10 3 R[8] : 3 10 7 3 R[9] : 3 8 11 3 R[10] : 8 1 4 8 R[11] : 4 6 9 4 R[12] : 6 2 5 6 R[13] : 5 2 7 5 R[14] : 6 5 9 6 R[15] : 10 5 7 10 R[16] : 8 4 11 8 R[17] : 9 5 10 9 Extending path in R[7] : 11 9 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 9 10 3 R[8] : 3 10 7 3 R[9] : 3 8 11 3 R[10] : 8 1 4 8 R[11] : 4 6 9 4 R[12] : 6 2 5 6 R[13] : 5 2 7 5 R[14] : 6 5 9 6 R[15] : 10 5 7 10 R[16] : 8 4 11 8 R[17] : 9 5 10 9 R[18] : 11 4 9 11 Extending path in R[7] : 11 10 Current picture : 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 1 1 0 Regions : R[0] : 0 7 2 0 R[1] : 0 2 1 0 R[2] : 0 1 8 0 R[3] : 0 8 3 0 R[4] : 0 3 7 0 R[5] : 1 2 6 1 R[6] : 1 6 4 1 R[7] : 3 11 10 3 R[8] : 3 10 7 3 R[9] : 3 8 11 3 R[10] : 8 1 4 8 R[11] : 4 6 9 4 R[12] : 6 2 5 6 R[13] : 5 2 7 5 R[14] : 6 5 9 6 R[15] : 10 5 7 10 R[16] : 8 4 11 8 R[17] : 9 5 10 9 R[18] : 11 4 9 11 R[19] : 11 9 10 11 G is planar.