/*
 * (C) Copyright 2018-2023, by Timofey Chudakov and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * See the CONTRIBUTORS.md file distributed with this work for additional
 * information regarding copyright ownership.
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Public License 2.0 which is available at
 * http://www.eclipse.org/legal/epl-2.0, or the
 * GNU Lesser General Public License v2.1 or later
 * which is available at
 * http://www.gnu.org/licenses/old-licenses/lgpl-2.1-standalone.html.
 *
 * SPDX-License-Identifier: EPL-2.0 OR LGPL-2.1-or-later
 */
package org.jgrapht.alg.planar;

import org.jgrapht.*;
import org.jgrapht.alg.interfaces.*;
import org.jgrapht.graph.*;
import org.junit.*;

import java.util.*;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

/**
 * Tests for the {@link BoyerMyrvoldPlanarityInspector}
 *
 * @author Timofey Chudakov
 */
public class BoyerMyrvoldPlanarityInspectorTest
{

    /**
     * Does a generic verification of the algorithm on the graph defined by the {@code edges}
     *
     * @param edges an array of the edge of the graph
     */
    private void testOnGraph(int[][] edges)
    {
        Graph<Integer, DefaultEdge> graph = TestUtil.createUndirected(edges);
        PlanarityTestingAlgorithm<Integer, DefaultEdge> inspector =
            new BoyerMyrvoldPlanarityInspector<>(graph);
        boolean planar = inspector.isPlanar();
        if (planar) {
            PlanarityTestingAlgorithm.Embedding<Integer, DefaultEdge> embedding =
                inspector.getEmbedding();
            testEmbedding(embedding);
        } else {
            Graph<Integer, DefaultEdge> subdivision = inspector.getKuratowskiSubdivision();
            boolean isSubdivision = GraphTests.isKuratowskiSubdivision(subdivision);
            assertTrue(isSubdivision);
        }
    }

    /**
     * Performs a basic verification of the embedding
     *
     * @param embedding a graph embedding
     */
    private void testEmbedding(PlanarityTestingAlgorithm.Embedding<Integer, DefaultEdge> embedding)
    {
        Graph<Integer, DefaultEdge> graph = embedding.getGraph();
        Map<DefaultEdge, Integer> cnt = new HashMap<>();
        int degreeSum = 0;
        for (int vertex : graph.vertexSet()) {
            List<DefaultEdge> edges = embedding.getEdgesAround(vertex);
            Set<DefaultEdge> set = new HashSet<>(edges);
            if (set.size() != edges.size()) {
                System.out.println(edges);
            }
            for (DefaultEdge edge : embedding.getEdgesAround(vertex)) {
                assertTrue(graph.containsEdge(edge));
                if (cnt.containsKey(edge)) {
                    cnt.put(edge, cnt.get(edge) + 1);
                } else {
                    cnt.put(edge, 1);
                }
            }
            degreeSum += embedding.getEdgesAround(vertex).size();
        }
        for (DefaultEdge edge : graph.edgeSet()) {
            assertTrue(cnt.containsKey(edge));
            if (cnt.get(edge) != 2) {
                System.out.println(graph.getEdgeSource(edge) + " " + graph.getEdgeTarget(edge));
            }
            assertEquals(2, (int) cnt.get(edge));
        }
        assertEquals(2 * graph.edgeSet().size(), degreeSum);
    }

    @Test(expected = IllegalArgumentException.class)
    public void testNonPlanarGraphNoEmbedding()
    {
        int[][] k_5 = { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 0, 4 }, { 1, 2 }, { 1, 3 }, { 1, 4 },
            { 2, 3 }, { 2, 4 }, { 3, 4 }, };
        Graph<Integer, DefaultEdge> graph = TestUtil.createUndirected(k_5);
        PlanarityTestingAlgorithm<Integer, DefaultEdge> algorithm =
            new BoyerMyrvoldPlanarityInspector<>(graph);
        algorithm.getEmbedding();
    }

    @Test(expected = IllegalArgumentException.class)
    public void testPlanarGraphNoKuratowskiSubdivision()
    {
        int[][] k_4 = { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }, };
        Graph<Integer, DefaultEdge> graph = TestUtil.createUndirected(k_4);
        PlanarityTestingAlgorithm<Integer, DefaultEdge> algorithm =
            new BoyerMyrvoldPlanarityInspector<>(graph);
        algorithm.getKuratowskiSubdivision();
    }

    @Test
    public void testPlanarity0()
    {
        int[][] edges = {};
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity1()
    {
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 0 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity2()
    {
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 1, 4 }, { 4, 5 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity3()
    {
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 0 }, { 1, 4 }, { 4, 5 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity4()
    {
        int[][] edges =
            { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 0, 2 }, { 0, 3 }, { 3, 1 }, { 1, 4 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity5()
    {
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 2 }, { 1, 5 }, { 5, 6 },
            { 6, 7 }, { 7, 5 }, };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity6()
    {
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 5, 0 }, { 5, 2 },
            { 4, 1 }, { 3, 0 }, };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity7()
    {
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 4, 2 }, { 2, 0 },
            { 0, 5 }, { 4, 1 }, { 5, 1 }, { 1, 3 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity8()
    {
        int[][] k_33 = { { 0, 3 }, { 0, 4 }, { 0, 5 }, { 1, 3 }, { 1, 4 }, { 1, 5 }, { 2, 3 },
            { 2, 4 }, { 2, 5 }, };
        testOnGraph(k_33);
    }

    @Test
    public void testPlanarity9()
    {
        int[][] edges = new int[][] { { 0, 2 }, { 1, 3 }, { 2, 6 }, { 3, 6 }, { 4, 0 }, { 5, 4 },
            { 6, 4 }, { 0, 5 }, { 1, 6 }, { 2, 3 }, { 3, 4 }, { 4, 1 }, { 5, 3 }, { 6, 5 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity10()
    {
        int[][] edges = new int[][] { { 0, 5 }, { 1, 6 }, { 2, 5 }, { 3, 2 }, { 4, 1 }, { 5, 4 },
            { 6, 0 }, { 0, 1 }, { 1, 2 }, { 2, 6 }, { 3, 1 }, { 4, 6 }, { 5, 6 }, { 6, 3 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity11()
    {
        int[][] edges = new int[][] { { 0, 5 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 6 }, { 5, 6 },
            { 6, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 }, { 4, 5 }, { 5, 3 }, { 6, 0 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity12()
    {
        int[][] edges = new int[][] { { 0, 6 }, { 1, 6 }, { 2, 6 }, { 3, 4 }, { 4, 1 }, { 5, 0 },
            { 6, 5 }, { 0, 4 }, { 1, 0 }, { 2, 0 }, { 3, 0 }, { 4, 2 }, { 5, 1 }, { 6, 3 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity13()
    {
        int[][] edges = new int[][] { { 0, 6 }, { 1, 0 }, { 2, 6 }, { 3, 6 }, { 4, 1 }, { 5, 2 },
            { 6, 1 }, { 0, 4 }, { 1, 5 }, { 2, 0 }, { 3, 5 }, { 4, 2 }, { 5, 6 }, { 6, 4 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity14()
    {
        int[][] edges = new int[][] { { 0, 4 }, { 1, 6 }, { 2, 0 }, { 3, 2 }, { 4, 2 }, { 5, 2 },
            { 6, 4 }, { 0, 3 }, { 1, 2 }, { 2, 6 }, { 3, 4 }, { 4, 5 }, { 5, 0 }, { 6, 0 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity15()
    {
        int[][] edges = new int[][] { { 0, 4 }, { 1, 3 }, { 2, 4 }, { 3, 6 }, { 4, 1 }, { 5, 1 },
            { 6, 5 }, { 0, 1 }, { 2, 3 }, { 3, 5 }, { 4, 6 }, { 5, 4 }, { 6, 0 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity16()
    {
        int[][] edges = new int[][] { { 0, 1 }, { 1, 5 }, { 2, 4 }, { 3, 9 }, { 4, 1 }, { 5, 9 },
            { 6, 2 }, { 7, 8 }, { 8, 6 }, { 9, 0 }, { 0, 6 }, { 1, 6 }, { 2, 8 }, { 3, 1 },
            { 4, 3 }, { 5, 7 }, { 6, 4 }, { 7, 3 }, { 8, 3 }, { 9, 7 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity17()
    {
        int[][] edges = new int[][] { { 0, 5 }, { 1, 0 }, { 2, 3 }, { 3, 5 }, { 4, 5 }, { 5, 8 },
            { 6, 5 }, { 7, 1 }, { 8, 7 }, { 9, 2 }, { 0, 2 }, { 1, 5 }, { 2, 6 }, { 3, 1 },
            { 4, 6 }, { 5, 2 }, { 6, 0 }, { 7, 4 }, { 8, 1 }, { 9, 7 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity18()
    {
        int[][] edges = new int[][] { { 0, 9 }, { 1, 9 }, { 2, 3 }, { 3, 1 }, { 4, 2 }, { 5, 7 },
            { 6, 8 }, { 7, 9 }, { 8, 9 }, { 9, 2 }, { 0, 7 }, { 1, 4 }, { 2, 0 }, { 3, 9 },
            { 4, 8 }, { 5, 4 }, { 6, 7 }, { 7, 8 }, { 8, 0 }, { 9, 4 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity19()
    {
        int[][] edges = new int[][] { { 0, 4 }, { 1, 3 }, { 2, 6 }, { 3, 2 }, { 4, 2 }, { 5, 2 },
            { 6, 4 }, { 7, 5 }, { 0, 2 }, { 1, 7 }, { 2, 7 }, { 3, 6 }, { 4, 7 }, { 5, 4 },
            { 6, 1 }, { 7, 0 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity20()
    {
        int[][] edges = new int[][] { { 0, 6 }, { 1, 6 }, { 2, 8 }, { 3, 6 }, { 4, 9 }, { 5, 7 },
            { 6, 7 }, { 7, 3 }, { 8, 6 }, { 9, 0 }, { 0, 7 }, { 1, 3 }, { 2, 6 }, { 3, 4 },
            { 4, 2 }, { 5, 3 }, { 6, 5 }, { 7, 8 }, { 8, 5 }, { 9, 8 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity21()
    {
        int[][] edges =
            new int[][] { { 0, 6 }, { 1, 7 }, { 2, 0 }, { 3, 6 }, { 4, 7 }, { 5, 0 }, { 6, 5 },
                { 7, 5 }, { 0, 7 }, { 1, 4 }, { 2, 1 }, { 3, 0 }, { 4, 6 }, { 5, 2 }, { 6, 2 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity22()
    {
        int[][] edges = new int[][] { { 0, 5 }, { 1, 7 }, { 2, 5 }, { 3, 5 }, { 4, 7 }, { 5, 6 },
            { 6, 1 }, { 7, 6 }, { 0, 2 }, { 1, 2 }, { 2, 6 }, { 3, 2 }, { 4, 6 }, { 5, 1 },
            { 6, 3 }, { 7, 3 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity23()
    {
        int[][] edges = new int[][] { { 0, 4 }, { 1, 0 }, { 2, 5 }, { 3, 7 }, { 4, 5 }, { 5, 7 },
            { 6, 2 }, { 7, 1 }, { 0, 2 }, { 1, 5 }, { 2, 3 }, { 3, 6 }, { 4, 6 }, { 5, 0 },
            { 6, 5 }, { 7, 2 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity24()
    {
        int[][] edges = new int[][] { { 0, 1 }, { 1, 2 }, { 2, 4 }, { 3, 6 }, { 4, 6 }, { 5, 3 },
            { 6, 2 }, { 0, 5 }, { 1, 6 }, { 2, 5 }, { 3, 4 }, { 4, 1 }, { 5, 1 }, { 6, 0 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity25()
    {
        int[][] edges = new int[][] { { 0, 4 }, { 1, 2 }, { 2, 3 }, { 3, 1 }, { 4, 3 }, { 5, 3 },
            { 6, 1 }, { 0, 3 }, { 1, 5 }, { 2, 5 }, { 3, 6 }, { 4, 2 }, { 5, 4 }, { 6, 0 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity26()
    {
        int[][] edges = new int[][] { { 0, 6 }, { 1, 4 }, { 2, 3 }, { 3, 4 }, { 4, 2 }, { 5, 0 },
            { 6, 4 }, { 0, 2 }, { 1, 5 }, { 2, 1 }, { 3, 0 }, { 4, 5 }, { 5, 2 }, { 6, 2 } };
        testOnGraph(edges);
    }

    @Test
    public void testPlanarity27()
    {
        int[][] edges = new int[][] { { 0, 5 }, { 1, 4 }, { 2, 7 }, { 3, 5 }, { 4, 2 }, { 5, 4 },
            { 6, 5 }, { 7, 1 }, { 0, 1 }, { 1, 2 }, { 2, 0 }, { 3, 6 }, { 4, 0 }, { 5, 7 },
            { 6, 7 }, { 7, 3 } };
        testOnGraph(edges);
    }

    /**
     * Triangulation of 50 points
     */
    @Test
    public void testPlanarity28()
    {
        int[][] edges = new int[][] { { 8, 1 }, { 1, 2 }, { 2, 4 }, { 4, 1 }, { 0, 1 }, { 4, 0 },
            { 2, 3 }, { 3, 4 }, { 8, 2 }, { 13, 3 }, { 3, 11 }, { 11, 13 }, { 4, 5 }, { 5, 0 },
            { 4, 6 }, { 6, 5 }, { 5, 7 }, { 7, 0 }, { 8, 3 }, { 14, 17 }, { 17, 4 }, { 4, 14 },
            { 6, 7 }, { 8, 11 }, { 6, 9 }, { 9, 7 }, { 6, 10 }, { 10, 9 }, { 9, 16 }, { 16, 7 },
            { 13, 14 }, { 14, 3 }, { 16, 10 }, { 10, 12 }, { 12, 16 }, { 11, 15 }, { 15, 13 },
            { 6, 12 }, { 8, 15 }, { 17, 6 }, { 20, 13 }, { 15, 20 }, { 17, 12 }, { 22, 8 },
            { 18, 12 }, { 17, 18 }, { 19, 14 }, { 13, 19 }, { 24, 14 }, { 19, 24 }, { 18, 16 },
            { 20, 21 }, { 21, 24 }, { 24, 20 }, { 18, 25 }, { 25, 16 }, { 20, 19 }, { 15, 21 },
            { 24, 26 }, { 26, 14 }, { 15, 22 }, { 22, 21 }, { 26, 17 }, { 22, 23 }, { 23, 21 },
            { 23, 29 }, { 29, 21 }, { 25, 17 }, { 26, 25 }, { 29, 32 }, { 32, 37 }, { 37, 29 },
            { 25, 31 }, { 31, 16 }, { 24, 27 }, { 27, 26 }, { 28, 26 }, { 27, 28 }, { 45, 23 },
            { 28, 25 }, { 33, 34 }, { 34, 24 }, { 24, 33 }, { 28, 31 }, { 37, 21 }, { 27, 30 },
            { 30, 28 }, { 21, 33 }, { 30, 35 }, { 35, 28 }, { 40, 34 }, { 34, 39 }, { 39, 40 },
            { 31, 36 }, { 36, 16 }, { 45, 29 }, { 40, 24 }, { 38, 34 }, { 33, 38 }, { 38, 39 },
            { 37, 33 }, { 35, 31 }, { 40, 30 }, { 27, 40 }, { 35, 36 }, { 37, 38 }, { 45, 32 },
            { 46, 38 }, { 37, 46 }, { 40, 47 }, { 47, 30 }, { 38, 44 }, { 44, 39 }, { 41, 35 },
            { 30, 41 }, { 42, 30 }, { 30, 43 }, { 43, 42 }, { 41, 36 }, { 42, 41 }, { 41, 48 },
            { 48, 36 }, { 44, 40 }, { 49, 42 }, { 43, 49 }, { 44, 47 }, { 43, 47 }, { 47, 49 },
            { 45, 46 }, { 37, 45 }, { 44, 46 }, { 46, 47 }, { 48, 42 }, { 49, 48 }, { 46, 49 },
            { 45, 49 } };
        testOnGraph(edges);
    }

    /**
     * Random not planar graph on 50 vertices
     */
    @Test
    public void testPlanarity29()
    {
        int[][] edges = new int[][] { { 0, 39 }, { 1, 31 }, { 2, 48 }, { 3, 11 }, { 4, 39 },
            { 5, 26 }, { 6, 18 }, { 7, 38 }, { 8, 0 }, { 9, 23 }, { 10, 48 }, { 11, 6 }, { 12, 4 },
            { 13, 46 }, { 14, 35 }, { 15, 25 }, { 16, 40 }, { 17, 7 }, { 18, 29 }, { 19, 10 },
            { 20, 19 }, { 21, 35 }, { 22, 8 }, { 23, 13 }, { 24, 8 }, { 25, 17 }, { 26, 47 },
            { 27, 37 }, { 28, 20 }, { 29, 4 }, { 30, 37 }, { 31, 21 }, { 32, 42 }, { 33, 32 },
            { 34, 44 }, { 35, 20 }, { 36, 47 }, { 37, 28 }, { 38, 8 }, { 39, 26 }, { 40, 22 },
            { 41, 28 }, { 42, 21 }, { 43, 7 }, { 44, 35 }, { 45, 17 }, { 46, 33 }, { 47, 18 },
            { 48, 1 }, { 49, 13 }, { 0, 34 }, { 1, 35 }, { 2, 5 }, { 3, 45 }, { 4, 24 }, { 5, 15 },
            { 6, 5 }, { 7, 8 }, { 8, 26 }, { 9, 42 } };
        testOnGraph(edges);
    }

    /**
     * Triangulation of 100 points
     */
    @Test
    public void testPlanarity30()
    {
        int[][] edges = new int[][] { { 1, 2 }, { 2, 3 }, { 3, 1 }, { 0, 2 }, { 1, 0 }, { 3, 5 },
            { 5, 1 }, { 1, 4 }, { 4, 0 }, { 7, 13 }, { 13, 2 }, { 2, 7 }, { 10, 11 }, { 11, 5 },
            { 5, 10 }, { 4, 12 }, { 12, 0 }, { 6, 7 }, { 2, 6 }, { 13, 18 }, { 18, 19 }, { 19, 13 },
            { 13, 3 }, { 32, 6 }, { 1, 8 }, { 8, 4 }, { 1, 9 }, { 9, 8 }, { 8, 12 }, { 11, 1 },
            { 14, 16 }, { 16, 11 }, { 11, 14 }, { 13, 20 }, { 20, 18 }, { 11, 9 }, { 19, 3 },
            { 10, 14 }, { 15, 8 }, { 9, 15 }, { 12, 26 }, { 26, 0 }, { 5, 21 }, { 21, 10 },
            { 16, 9 }, { 23, 24 }, { 24, 21 }, { 21, 23 }, { 15, 12 }, { 16, 15 }, { 34, 15 },
            { 15, 17 }, { 17, 34 }, { 19, 22 }, { 22, 3 }, { 16, 17 }, { 3, 21 }, { 34, 12 },
            { 7, 20 }, { 21, 14 }, { 32, 18 }, { 20, 32 }, { 30, 19 }, { 18, 30 }, { 32, 7 },
            { 24, 25 }, { 25, 21 }, { 22, 21 }, { 22, 23 }, { 19, 27 }, { 27, 22 }, { 25, 14 },
            { 28, 22 }, { 27, 28 }, { 25, 29 }, { 29, 14 }, { 28, 23 }, { 29, 36 }, { 36, 14 },
            { 23, 31 }, { 31, 24 }, { 36, 16 }, { 26, 54 }, { 54, 0 }, { 28, 31 }, { 31, 25 },
            { 33, 27 }, { 27, 30 }, { 30, 33 }, { 36, 17 }, { 33, 28 }, { 35, 29 }, { 29, 31 },
            { 31, 35 }, { 38, 30 }, { 30, 32 }, { 32, 38 }, { 31, 33 }, { 33, 35 }, { 97, 32 },
            { 34, 26 }, { 45, 29 }, { 35, 45 }, { 34, 37 }, { 37, 26 }, { 38, 33 }, { 36, 34 },
            { 55, 35 }, { 33, 55 }, { 52, 36 }, { 36, 39 }, { 39, 52 }, { 29, 39 }, { 37, 40 },
            { 40, 26 }, { 38, 55 }, { 44, 34 }, { 36, 44 }, { 29, 42 }, { 42, 39 }, { 44, 37 },
            { 37, 43 }, { 43, 40 }, { 40, 41 }, { 41, 26 }, { 47, 57 }, { 57, 42 }, { 42, 47 },
            { 41, 54 }, { 49, 42 }, { 42, 45 }, { 45, 49 }, { 43, 41 }, { 44, 43 }, { 46, 50 },
            { 50, 44 }, { 44, 46 }, { 50, 43 }, { 38, 56 }, { 56, 55 }, { 36, 46 }, { 57, 39 },
            { 50, 41 }, { 45, 48 }, { 48, 49 }, { 49, 47 }, { 35, 48 }, { 53, 47 }, { 49, 53 },
            { 48, 66 }, { 66, 49 }, { 52, 46 }, { 46, 51 }, { 51, 50 }, { 50, 54 }, { 52, 51 },
            { 57, 58 }, { 58, 52 }, { 52, 57 }, { 53, 57 }, { 55, 48 }, { 56, 65 }, { 65, 67 },
            { 67, 56 }, { 51, 54 }, { 55, 69 }, { 69, 48 }, { 67, 55 }, { 65, 38 }, { 32, 65 },
            { 58, 60 }, { 60, 52 }, { 70, 57 }, { 53, 70 }, { 60, 61 }, { 61, 52 }, { 57, 59 },
            { 59, 58 }, { 59, 60 }, { 66, 70 }, { 53, 66 }, { 61, 51 }, { 70, 59 }, { 61, 54 },
            { 63, 60 }, { 60, 62 }, { 62, 63 }, { 61, 72 }, { 72, 54 }, { 59, 62 }, { 63, 61 },
            { 62, 64 }, { 64, 63 }, { 64, 61 }, { 64, 74 }, { 74, 61 }, { 70, 75 }, { 75, 59 },
            { 68, 55 }, { 67, 68 }, { 69, 66 }, { 83, 65 }, { 32, 83 }, { 68, 69 }, { 71, 67 },
            { 65, 71 }, { 76, 66 }, { 69, 76 }, { 71, 68 }, { 75, 62 }, { 73, 78 }, { 78, 71 },
            { 71, 73 }, { 77, 62 }, { 75, 77 }, { 71, 80 }, { 80, 68 }, { 76, 84 }, { 84, 66 },
            { 78, 82 }, { 82, 71 }, { 72, 79 }, { 79, 54 }, { 65, 73 }, { 74, 72 }, { 77, 64 },
            { 74, 81 }, { 81, 72 }, { 84, 70 }, { 84, 75 }, { 73, 83 }, { 83, 78 }, { 85, 64 },
            { 77, 85 }, { 80, 86 }, { 86, 69 }, { 69, 80 }, { 85, 74 }, { 84, 89 }, { 89, 75 },
            { 86, 76 }, { 88, 78 }, { 83, 88 }, { 81, 79 }, { 88, 82 }, { 81, 93 }, { 93, 79 },
            { 82, 80 }, { 87, 80 }, { 82, 87 }, { 89, 96 }, { 96, 75 }, { 91, 80 }, { 87, 91 },
            { 85, 81 }, { 91, 86 }, { 93, 85 }, { 77, 93 }, { 86, 90 }, { 90, 76 }, { 90, 84 },
            { 88, 87 }, { 92, 87 }, { 88, 92 }, { 97, 83 }, { 96, 77 }, { 90, 89 }, { 94, 86 },
            { 91, 94 }, { 94, 95 }, { 95, 86 }, { 99, 87 }, { 92, 99 }, { 97, 99 }, { 92, 97 },
            { 83, 92 }, { 95, 90 }, { 95, 98 }, { 98, 90 }, { 91, 99 }, { 99, 94 }, { 98, 89 },
            { 96, 93 }, { 94, 98 }, { 98, 96 }, { 99, 98 }, { 99, 96 } };
        testOnGraph(edges);
    }

    /**
     * Random not planar graph on 100 vertices
     */
    @Test
    public void testPlanarity31()
    {
        int[][] edges = new int[][] { { 0, 83 }, { 1, 13 }, { 2, 97 }, { 3, 4 }, { 4, 53 },
            { 5, 7 }, { 6, 65 }, { 7, 16 }, { 8, 46 }, { 9, 5 }, { 10, 92 }, { 11, 16 }, { 12, 84 },
            { 13, 88 }, { 14, 41 }, { 15, 21 }, { 16, 54 }, { 17, 84 }, { 18, 82 }, { 19, 38 },
            { 20, 24 }, { 21, 59 }, { 22, 36 }, { 23, 8 }, { 24, 38 }, { 25, 59 }, { 26, 80 },
            { 27, 18 }, { 28, 62 }, { 29, 80 }, { 30, 20 }, { 31, 2 }, { 32, 69 }, { 33, 10 },
            { 34, 84 }, { 35, 60 }, { 36, 57 }, { 37, 0 }, { 38, 46 }, { 39, 8 }, { 40, 33 },
            { 41, 6 }, { 42, 61 }, { 43, 70 }, { 44, 71 }, { 45, 87 }, { 46, 62 }, { 47, 71 },
            { 48, 80 }, { 49, 24 }, { 50, 58 }, { 51, 11 }, { 52, 23 }, { 53, 66 }, { 54, 81 },
            { 55, 59 }, { 56, 13 }, { 57, 83 }, { 58, 79 }, { 59, 99 }, { 60, 58 }, { 61, 0 },
            { 62, 32 }, { 63, 36 }, { 64, 20 }, { 65, 82 }, { 66, 22 }, { 67, 21 }, { 68, 88 },
            { 69, 23 }, { 70, 99 }, { 71, 93 }, { 72, 81 }, { 73, 8 }, { 74, 54 }, { 75, 15 },
            { 76, 9 }, { 77, 50 }, { 78, 27 }, { 79, 6 }, { 80, 0 }, { 81, 29 }, { 82, 99 },
            { 83, 6 }, { 84, 48 }, { 85, 37 }, { 86, 11 }, { 87, 39 }, { 88, 40 }, { 89, 36 },
            { 90, 32 }, { 91, 73 }, { 92, 97 }, { 93, 10 }, { 94, 67 }, { 95, 85 }, { 96, 30 },
            { 97, 93 }, { 98, 3 }, { 99, 80 }, { 0, 4 }, { 1, 64 }, { 2, 92 }, { 3, 74 }, { 4, 30 },
            { 5, 46 }, { 6, 76 }, { 7, 75 }, { 8, 72 }, { 9, 79 }, { 10, 57 }, { 11, 42 },
            { 12, 58 }, { 13, 12 }, { 14, 46 }, { 15, 74 }, { 16, 96 }, { 17, 89 }, { 18, 75 },
            { 19, 50 } };
        testOnGraph(edges);
    }

    /**
     * Triangulation of 150 points
     */
    @Test
    public void testPlanarity32()
    {
        int[][] edges = new int[][] { { 1, 0 }, { 0, 5 }, { 5, 1 }, { 0, 2 }, { 2, 4 }, { 4, 0 },
            { 1, 3 }, { 3, 7 }, { 7, 1 }, { 13, 16 }, { 16, 4 }, { 4, 13 }, { 6, 2 }, { 5, 3 },
            { 10, 4 }, { 2, 10 }, { 5, 8 }, { 8, 3 }, { 6, 10 }, { 0, 9 }, { 9, 5 }, { 12, 3 },
            { 8, 12 }, { 7, 11 }, { 11, 1 }, { 27, 5 }, { 9, 27 }, { 12, 7 }, { 10, 13 },
            { 16, 17 }, { 17, 4 }, { 20, 6 }, { 24, 7 }, { 12, 24 }, { 14, 27 }, { 9, 14 },
            { 0, 14 }, { 7, 15 }, { 15, 11 }, { 21, 16 }, { 13, 21 }, { 27, 8 }, { 20, 25 },
            { 25, 10 }, { 10, 20 }, { 17, 18 }, { 18, 0 }, { 0, 17 }, { 18, 14 }, { 15, 24 },
            { 24, 11 }, { 18, 22 }, { 22, 29 }, { 29, 18 }, { 10, 21 }, { 19, 12 }, { 8, 19 },
            { 21, 22 }, { 22, 16 }, { 49, 12 }, { 19, 49 }, { 22, 17 }, { 27, 19 }, { 26, 10 },
            { 25, 26 }, { 28, 14 }, { 18, 28 }, { 21, 23 }, { 23, 22 }, { 52, 20 }, { 26, 23 },
            { 21, 26 }, { 26, 37 }, { 37, 23 }, { 80, 24 }, { 24, 73 }, { 73, 80 }, { 43, 22 },
            { 23, 43 }, { 22, 30 }, { 30, 29 }, { 31, 19 }, { 27, 31 }, { 34, 14 }, { 28, 34 },
            { 34, 27 }, { 29, 28 }, { 30, 36 }, { 36, 29 }, { 33, 26 }, { 25, 33 }, { 36, 28 },
            { 32, 26 }, { 33, 32 }, { 40, 19 }, { 31, 40 }, { 33, 46 }, { 46, 32 }, { 38, 31 },
            { 27, 38 }, { 32, 37 }, { 37, 43 }, { 35, 25 }, { 20, 35 }, { 34, 38 }, { 52, 56 },
            { 56, 35 }, { 35, 52 }, { 45, 31 }, { 38, 45 }, { 35, 33 }, { 42, 28 }, { 36, 42 },
            { 43, 47 }, { 47, 22 }, { 42, 34 }, { 44, 59 }, { 59, 42 }, { 42, 44 }, { 36, 39 },
            { 39, 42 }, { 30, 39 }, { 41, 19 }, { 40, 41 }, { 46, 37 }, { 45, 40 }, { 42, 45 },
            { 45, 34 }, { 41, 49 }, { 47, 30 }, { 49, 24 }, { 47, 39 }, { 39, 44 }, { 54, 46 },
            { 33, 54 }, { 51, 43 }, { 37, 51 }, { 60, 40 }, { 45, 60 }, { 47, 44 }, { 45, 57 },
            { 57, 60 }, { 46, 53 }, { 53, 37 }, { 48, 44 }, { 47, 48 }, { 51, 47 }, { 48, 59 },
            { 35, 54 }, { 42, 57 }, { 41, 50 }, { 50, 49 }, { 63, 49 }, { 49, 61 }, { 61, 63 },
            { 62, 48 }, { 48, 51 }, { 51, 62 }, { 60, 50 }, { 41, 60 }, { 53, 51 }, { 65, 51 },
            { 53, 65 }, { 54, 53 }, { 55, 64 }, { 64, 54 }, { 54, 55 }, { 35, 55 }, { 56, 58 },
            { 58, 55 }, { 55, 56 }, { 58, 64 }, { 119, 52 }, { 64, 53 }, { 61, 50 }, { 60, 61 },
            { 70, 56 }, { 52, 70 }, { 59, 57 }, { 70, 58 }, { 62, 59 }, { 69, 74 }, { 74, 59 },
            { 59, 69 }, { 51, 68 }, { 68, 62 }, { 63, 24 }, { 65, 68 }, { 60, 67 }, { 67, 61 },
            { 65, 66 }, { 66, 68 }, { 73, 63 }, { 63, 67 }, { 67, 73 }, { 64, 65 }, { 68, 69 },
            { 69, 62 }, { 64, 88 }, { 88, 65 }, { 70, 64 }, { 59, 71 }, { 71, 57 }, { 78, 88 },
            { 64, 78 }, { 71, 72 }, { 72, 57 }, { 83, 68 }, { 66, 83 }, { 72, 60 }, { 70, 78 },
            { 75, 59 }, { 74, 75 }, { 79, 69 }, { 68, 79 }, { 76, 60 }, { 72, 76 }, { 119, 70 },
            { 75, 81 }, { 81, 71 }, { 71, 75 }, { 76, 77 }, { 77, 60 }, { 80, 11 }, { 81, 84 },
            { 84, 85 }, { 85, 81 }, { 90, 74 }, { 74, 79 }, { 79, 90 }, { 77, 67 }, { 82, 67 },
            { 77, 82 }, { 74, 81 }, { 86, 67 }, { 82, 86 }, { 88, 66 }, { 85, 71 }, { 83, 79 },
            { 85, 72 }, { 85, 76 }, { 95, 78 }, { 78, 93 }, { 93, 95 }, { 86, 73 }, { 90, 81 },
            { 76, 100 }, { 100, 77 }, { 83, 96 }, { 96, 79 }, { 85, 100 }, { 88, 83 }, { 100, 101 },
            { 101, 77 }, { 90, 85 }, { 84, 90 }, { 87, 73 }, { 86, 87 }, { 87, 80 }, { 90, 100 },
            { 87, 89 }, { 89, 80 }, { 88, 92 }, { 92, 97 }, { 97, 88 }, { 86, 91 }, { 91, 87 },
            { 101, 82 }, { 118, 89 }, { 89, 98 }, { 98, 118 }, { 78, 92 }, { 91, 89 }, { 95, 92 },
            { 91, 98 }, { 88, 94 }, { 94, 83 }, { 94, 96 }, { 119, 78 }, { 96, 90 }, { 95, 97 },
            { 97, 94 }, { 99, 93 }, { 78, 99 }, { 105, 90 }, { 96, 105 }, { 104, 110 }, { 110, 97 },
            { 97, 104 }, { 86, 98 }, { 99, 95 }, { 99, 104 }, { 104, 95 }, { 118, 80 }, { 99, 103 },
            { 103, 104 }, { 101, 102 }, { 102, 82 }, { 127, 97 }, { 110, 127 }, { 102, 86 },
            { 100, 107 }, { 107, 101 }, { 102, 98 }, { 104, 109 }, { 109, 110 }, { 107, 117 },
            { 117, 106 }, { 106, 107 }, { 78, 103 }, { 105, 113 }, { 113, 90 }, { 108, 103 },
            { 78, 108 }, { 111, 113 }, { 105, 111 }, { 97, 120 }, { 120, 94 }, { 101, 106 },
            { 106, 102 }, { 116, 102 }, { 106, 116 }, { 103, 109 }, { 102, 112 }, { 112, 98 },
            { 108, 109 }, { 94, 115 }, { 115, 96 }, { 108, 110 }, { 115, 105 }, { 119, 108 },
            { 113, 100 }, { 111, 114 }, { 114, 113 }, { 123, 107 }, { 100, 123 }, { 113, 123 },
            { 117, 112 }, { 112, 116 }, { 116, 117 }, { 105, 114 }, { 115, 120 }, { 120, 122 },
            { 122, 115 }, { 115, 114 }, { 122, 129 }, { 129, 115 }, { 119, 124 }, { 124, 108 },
            { 121, 112 }, { 117, 121 }, { 124, 126 }, { 126, 108 }, { 112, 118 }, { 129, 114 },
            { 149, 118 }, { 118, 134 }, { 134, 149 }, { 123, 131 }, { 131, 107 }, { 126, 110 },
            { 121, 118 }, { 129, 113 }, { 121, 125 }, { 125, 118 }, { 126, 127 }, { 131, 117 },
            { 127, 120 }, { 143, 117 }, { 131, 143 }, { 137, 124 }, { 124, 139 }, { 139, 137 },
            { 127, 122 }, { 127, 133 }, { 133, 140 }, { 140, 127 }, { 125, 134 }, { 132, 124 },
            { 137, 132 }, { 128, 123 }, { 113, 128 }, { 133, 126 }, { 126, 132 }, { 132, 133 },
            { 128, 131 }, { 130, 113 }, { 129, 130 }, { 130, 128 }, { 140, 122 }, { 138, 128 },
            { 130, 138 }, { 129, 138 }, { 135, 121 }, { 117, 135 }, { 135, 125 }, { 132, 140 },
            { 119, 139 }, { 138, 131 }, { 135, 134 }, { 149, 80 }, { 148, 131 }, { 138, 148 },
            { 135, 136 }, { 136, 134 }, { 142, 129 }, { 122, 142 }, { 136, 149 }, { 137, 140 },
            { 143, 135 }, { 141, 137 }, { 139, 141 }, { 142, 138 }, { 140, 142 }, { 145, 137 },
            { 141, 145 }, { 144, 140 }, { 137, 144 }, { 147, 139 }, { 142, 148 }, { 144, 142 },
            { 143, 136 }, { 144, 148 }, { 143, 149 }, { 145, 144 }, { 147, 144 }, { 145, 147 },
            { 147, 141 }, { 131, 146 }, { 146, 143 }, { 147, 148 }, { 149, 146 }, { 146, 148 },
            { 148, 149 } };
        testOnGraph(edges);
    }

    /**
     * Random not planar graph on 150 vertices
     */
    @Test
    public void testPlanarity33()
    {
        int[][] edges = new int[][] { { 0, 113 }, { 1, 107 }, { 2, 95 }, { 3, 77 }, { 4, 49 },
            { 5, 61 }, { 6, 25 }, { 7, 3 }, { 8, 5 }, { 9, 129 }, { 10, 14 }, { 11, 92 },
            { 12, 135 }, { 13, 56 }, { 14, 145 }, { 15, 17 }, { 16, 110 }, { 17, 39 }, { 18, 90 },
            { 19, 65 }, { 20, 121 }, { 21, 64 }, { 22, 75 }, { 23, 65 }, { 24, 91 }, { 25, 79 },
            { 26, 83 }, { 27, 75 }, { 28, 87 }, { 29, 32 }, { 30, 69 }, { 31, 4 }, { 32, 75 },
            { 33, 112 }, { 34, 115 }, { 35, 23 }, { 36, 86 }, { 37, 3 }, { 38, 122 }, { 39, 104 },
            { 40, 52 }, { 41, 62 }, { 42, 49 }, { 43, 32 }, { 44, 79 }, { 45, 125 }, { 46, 48 },
            { 47, 120 }, { 48, 5 }, { 49, 1 }, { 50, 60 }, { 51, 74 }, { 52, 55 }, { 53, 130 },
            { 54, 0 }, { 55, 28 }, { 56, 29 }, { 57, 80 }, { 58, 60 }, { 59, 92 }, { 60, 7 },
            { 61, 93 }, { 62, 25 }, { 63, 143 }, { 64, 88 }, { 65, 52 }, { 66, 144 }, { 67, 50 },
            { 68, 1 }, { 69, 68 }, { 70, 35 }, { 71, 54 }, { 72, 67 }, { 73, 87 }, { 74, 97 },
            { 75, 113 }, { 76, 49 }, { 77, 54 }, { 78, 29 }, { 79, 91 }, { 80, 3 }, { 81, 139 },
            { 82, 17 }, { 83, 111 }, { 84, 66 }, { 85, 20 }, { 86, 76 }, { 87, 29 }, { 88, 6 },
            { 89, 4 }, { 90, 131 }, { 91, 85 }, { 92, 19 }, { 93, 133 }, { 94, 130 }, { 95, 59 },
            { 96, 120 }, { 97, 59 }, { 98, 79 }, { 99, 90 }, { 100, 25 }, { 101, 54 }, { 102, 24 },
            { 103, 138 }, { 104, 137 }, { 105, 88 }, { 106, 144 }, { 107, 114 }, { 108, 75 },
            { 109, 49 }, { 110, 114 }, { 111, 6 }, { 112, 98 }, { 113, 132 }, { 114, 124 },
            { 115, 84 }, { 116, 28 }, { 117, 32 }, { 118, 120 }, { 119, 101 }, { 120, 85 },
            { 121, 64 }, { 122, 36 }, { 123, 133 }, { 124, 129 }, { 125, 18 }, { 126, 45 },
            { 127, 125 }, { 128, 137 }, { 129, 144 }, { 130, 149 }, { 131, 34 }, { 132, 90 },
            { 133, 66 }, { 134, 89 }, { 135, 75 }, { 136, 51 }, { 137, 83 }, { 138, 129 },
            { 139, 109 }, { 140, 13 }, { 141, 118 }, { 142, 114 }, { 143, 56 }, { 144, 97 },
            { 145, 137 }, { 146, 72 }, { 147, 68 }, { 148, 80 }, { 149, 84 }, { 0, 63 }, { 1, 32 },
            { 2, 18 }, { 3, 12 }, { 4, 130 }, { 5, 101 }, { 6, 98 }, { 7, 72 }, { 8, 48 },
            { 9, 24 }, { 10, 81 }, { 11, 47 }, { 12, 126 }, { 13, 125 }, { 14, 2 } };
        testOnGraph(edges);
    }

    /**
     * Triangulation of 200 points
     */
    @Test
    public void testPlanarity34()
    {
        int[][] edges = new int[][] { { 9, 13 }, { 13, 10 }, { 10, 9 }, { 1, 2 }, { 2, 0 },
            { 0, 1 }, { 0, 3 }, { 3, 4 }, { 4, 0 }, { 2, 12 }, { 12, 0 }, { 7, 2 }, { 1, 7 },
            { 7, 12 }, { 4, 5 }, { 5, 0 }, { 8, 4 }, { 3, 8 }, { 5, 6 }, { 6, 0 }, { 8, 11 },
            { 11, 4 }, { 12, 3 }, { 10, 4 }, { 4, 9 }, { 21, 7 }, { 1, 21 }, { 20, 6 }, { 6, 15 },
            { 15, 20 }, { 10, 5 }, { 12, 17 }, { 17, 3 }, { 13, 16 }, { 16, 10 }, { 8, 17 },
            { 17, 11 }, { 17, 29 }, { 29, 11 }, { 11, 9 }, { 55, 1 }, { 16, 5 }, { 19, 24 },
            { 24, 18 }, { 18, 19 }, { 14, 6 }, { 5, 14 }, { 13, 22 }, { 22, 16 }, { 24, 6 },
            { 14, 24 }, { 16, 19 }, { 19, 5 }, { 5, 18 }, { 18, 14 }, { 9, 22 }, { 29, 9 },
            { 21, 27 }, { 27, 7 }, { 27, 12 }, { 23, 15 }, { 6, 23 }, { 31, 20 }, { 15, 31 },
            { 22, 19 }, { 27, 17 }, { 22, 32 }, { 32, 19 }, { 31, 25 }, { 25, 20 }, { 23, 33 },
            { 33, 34 }, { 34, 23 }, { 24, 23 }, { 27, 30 }, { 30, 17 }, { 26, 23 }, { 24, 26 },
            { 32, 36 }, { 36, 19 }, { 26, 33 }, { 87, 25 }, { 25, 28 }, { 28, 87 }, { 29, 22 },
            { 1, 39 }, { 39, 21 }, { 29, 32 }, { 27, 40 }, { 40, 30 }, { 36, 24 }, { 34, 47 },
            { 47, 31 }, { 31, 34 }, { 30, 29 }, { 21, 38 }, { 38, 27 }, { 31, 28 }, { 46, 65 },
            { 65, 34 }, { 34, 46 }, { 36, 41 }, { 41, 24 }, { 27, 35 }, { 35, 40 }, { 34, 15 },
            { 44, 30 }, { 40, 44 }, { 32, 42 }, { 42, 36 }, { 41, 26 }, { 44, 29 }, { 41, 46 },
            { 46, 26 }, { 37, 51 }, { 51, 38 }, { 38, 37 }, { 38, 35 }, { 21, 37 }, { 38, 43 },
            { 43, 35 }, { 33, 46 }, { 39, 55 }, { 55, 37 }, { 37, 39 }, { 29, 53 }, { 53, 32 },
            { 54, 28 }, { 31, 54 }, { 45, 60 }, { 60, 42 }, { 42, 45 }, { 42, 49 }, { 49, 36 },
            { 43, 40 }, { 43, 52 }, { 52, 57 }, { 57, 43 }, { 44, 50 }, { 50, 29 }, { 56, 44 },
            { 40, 56 }, { 32, 45 }, { 52, 48 }, { 48, 51 }, { 51, 52 }, { 49, 41 }, { 43, 48 },
            { 47, 54 }, { 49, 58 }, { 58, 41 }, { 50, 53 }, { 38, 48 }, { 60, 49 }, { 68, 73 },
            { 73, 54 }, { 54, 68 }, { 53, 45 }, { 70, 44 }, { 56, 70 }, { 43, 56 }, { 53, 60 },
            { 55, 62 }, { 62, 37 }, { 58, 66 }, { 66, 41 }, { 78, 59 }, { 59, 69 }, { 69, 78 },
            { 61, 64 }, { 64, 65 }, { 65, 61 }, { 51, 59 }, { 59, 52 }, { 56, 63 }, { 63, 70 },
            { 67, 37 }, { 62, 67 }, { 74, 44 }, { 70, 74 }, { 60, 79 }, { 79, 58 }, { 58, 60 },
            { 57, 63 }, { 63, 43 }, { 161, 55 }, { 41, 61 }, { 61, 46 }, { 65, 47 }, { 59, 57 },
            { 67, 51 }, { 71, 54 }, { 47, 71 }, { 72, 74 }, { 70, 72 }, { 69, 51 }, { 67, 69 },
            { 74, 50 }, { 73, 28 }, { 66, 61 }, { 65, 71 }, { 75, 65 }, { 64, 75 }, { 61, 75 },
            { 66, 80 }, { 80, 61 }, { 78, 57 }, { 55, 81 }, { 81, 62 }, { 78, 86 }, { 86, 57 },
            { 77, 68 }, { 54, 77 }, { 74, 85 }, { 85, 50 }, { 81, 67 }, { 85, 53 }, { 81, 69 },
            { 71, 77 }, { 73, 87 }, { 53, 79 }, { 86, 63 }, { 79, 66 }, { 82, 83 }, { 83, 77 },
            { 77, 82 }, { 75, 76 }, { 76, 65 }, { 63, 84 }, { 84, 70 }, { 76, 71 }, { 71, 82 },
            { 76, 82 }, { 72, 84 }, { 84, 74 }, { 83, 68 }, { 75, 80 }, { 80, 90 }, { 90, 75 },
            { 79, 88 }, { 88, 66 }, { 81, 99 }, { 99, 69 }, { 90, 76 }, { 73, 83 }, { 83, 87 },
            { 84, 92 }, { 92, 74 }, { 99, 78 }, { 53, 89 }, { 89, 79 }, { 192, 25 }, { 87, 192 },
            { 85, 89 }, { 88, 80 }, { 55, 112 }, { 112, 81 }, { 88, 90 }, { 86, 84 }, { 92, 85 },
            { 86, 98 }, { 98, 84 }, { 90, 82 }, { 111, 92 }, { 92, 106 }, { 106, 111 }, { 90, 97 },
            { 97, 82 }, { 88, 101 }, { 101, 109 }, { 109, 88 }, { 89, 93 }, { 93, 79 }, { 78, 91 },
            { 91, 86 }, { 97, 83 }, { 148, 87 }, { 87, 94 }, { 94, 148 }, { 92, 89 }, { 91, 95 },
            { 95, 86 }, { 93, 101 }, { 101, 79 }, { 99, 91 }, { 95, 96 }, { 96, 86 }, { 83, 94 },
            { 97, 104 }, { 104, 83 }, { 98, 92 }, { 96, 98 }, { 98, 106 }, { 99, 100 }, { 100, 91 },
            { 97, 103 }, { 103, 104 }, { 96, 100 }, { 100, 113 }, { 113, 96 }, { 111, 89 },
            { 124, 97 }, { 90, 124 }, { 95, 100 }, { 96, 110 }, { 110, 98 }, { 81, 102 },
            { 102, 105 }, { 105, 81 }, { 109, 90 }, { 108, 94 }, { 83, 108 }, { 118, 105 },
            { 105, 112 }, { 112, 118 }, { 105, 99 }, { 99, 118 }, { 118, 122 }, { 122, 99 },
            { 129, 148 }, { 148, 117 }, { 117, 129 }, { 104, 108 }, { 148, 108 }, { 108, 117 },
            { 93, 107 }, { 107, 101 }, { 111, 93 }, { 107, 109 }, { 116, 93 }, { 111, 116 },
            { 127, 109 }, { 109, 123 }, { 123, 127 }, { 110, 106 }, { 125, 104 }, { 103, 125 },
            { 111, 115 }, { 115, 116 }, { 109, 119 }, { 119, 123 }, { 110, 113 }, { 113, 114 },
            { 114, 110 }, { 110, 121 }, { 121, 106 }, { 131, 110 }, { 114, 131 }, { 102, 112 },
            { 106, 115 }, { 55, 126 }, { 126, 112 }, { 116, 107 }, { 122, 100 }, { 116, 119 },
            { 119, 107 }, { 122, 113 }, { 122, 114 }, { 104, 117 }, { 124, 103 }, { 115, 120 },
            { 120, 116 }, { 121, 115 }, { 109, 124 }, { 115, 130 }, { 130, 120 }, { 120, 119 },
            { 135, 119 }, { 120, 135 }, { 121, 130 }, { 128, 117 }, { 104, 128 }, { 122, 131 },
            { 126, 118 }, { 131, 121 }, { 126, 133 }, { 133, 118 }, { 124, 125 }, { 146, 118 },
            { 133, 146 }, { 125, 128 }, { 137, 148 }, { 129, 137 }, { 127, 124 }, { 130, 135 },
            { 127, 136 }, { 136, 124 }, { 161, 126 }, { 132, 125 }, { 124, 132 }, { 135, 123 },
            { 128, 129 }, { 134, 137 }, { 137, 128 }, { 128, 134 }, { 139, 123 }, { 135, 139 },
            { 130, 131 }, { 131, 135 }, { 132, 134 }, { 134, 125 }, { 122, 138 }, { 138, 131 },
            { 146, 122 }, { 136, 132 }, { 139, 127 }, { 135, 140 }, { 140, 157 }, { 157, 135 },
            { 136, 134 }, { 138, 140 }, { 140, 131 }, { 144, 153 }, { 153, 136 }, { 136, 144 },
            { 139, 136 }, { 161, 133 }, { 139, 143 }, { 143, 136 }, { 137, 142 }, { 142, 148 },
            { 140, 141 }, { 141, 157 }, { 146, 138 }, { 135, 160 }, { 160, 139 }, { 138, 141 },
            { 134, 142 }, { 145, 159 }, { 159, 144 }, { 144, 145 }, { 143, 144 }, { 153, 142 },
            { 134, 153 }, { 139, 145 }, { 145, 143 }, { 191, 192 }, { 192, 148 }, { 148, 191 },
            { 138, 147 }, { 147, 149 }, { 149, 138 }, { 146, 147 }, { 149, 141 }, { 133, 151 },
            { 151, 146 }, { 167, 155 }, { 155, 156 }, { 156, 167 }, { 153, 163 }, { 163, 150 },
            { 150, 153 }, { 149, 152 }, { 152, 155 }, { 155, 149 }, { 146, 152 }, { 152, 147 },
            { 150, 148 }, { 142, 150 }, { 159, 153 }, { 151, 156 }, { 156, 146 }, { 139, 154 },
            { 154, 145 }, { 163, 148 }, { 157, 160 }, { 154, 158 }, { 158, 145 }, { 156, 152 },
            { 167, 149 }, { 161, 151 }, { 149, 164 }, { 164, 141 }, { 160, 154 }, { 162, 171 },
            { 171, 158 }, { 158, 162 }, { 158, 159 }, { 164, 157 }, { 159, 163 }, { 160, 162 },
            { 162, 154 }, { 165, 148 }, { 163, 165 }, { 161, 174 }, { 174, 151 }, { 161, 173 },
            { 173, 174 }, { 164, 166 }, { 166, 157 }, { 172, 148 }, { 165, 172 }, { 171, 159 },
            { 166, 160 }, { 166, 175 }, { 175, 160 }, { 181, 161 }, { 169, 163 }, { 159, 169 },
            { 164, 168 }, { 168, 170 }, { 170, 164 }, { 170, 166 }, { 165, 169 }, { 169, 172 },
            { 167, 168 }, { 164, 167 }, { 175, 162 }, { 156, 174 }, { 174, 176 }, { 176, 156 },
            { 180, 184 }, { 184, 172 }, { 172, 180 }, { 170, 178 }, { 178, 166 }, { 171, 169 },
            { 176, 167 }, { 180, 169 }, { 171, 180 }, { 187, 177 }, { 177, 186 }, { 186, 187 },
            { 168, 176 }, { 176, 170 }, { 175, 171 }, { 181, 173 }, { 177, 178 }, { 178, 186 },
            { 176, 179 }, { 179, 170 }, { 184, 191 }, { 191, 172 }, { 177, 175 }, { 166, 177 },
            { 174, 188 }, { 188, 176 }, { 175, 185 }, { 185, 171 }, { 179, 182 }, { 182, 170 },
            { 181, 174 }, { 182, 183 }, { 183, 170 }, { 188, 179 }, { 181, 188 }, { 183, 178 },
            { 199, 181 }, { 183, 186 }, { 188, 199 }, { 199, 179 }, { 185, 193 }, { 193, 171 },
            { 187, 189 }, { 189, 185 }, { 185, 187 }, { 193, 180 }, { 186, 189 }, { 187, 175 },
            { 199, 182 }, { 183, 199 }, { 199, 186 }, { 189, 195 }, { 195, 185 }, { 190, 184 },
            { 180, 190 }, { 186, 195 }, { 194, 184 }, { 190, 194 }, { 193, 190 }, { 192, 194 },
            { 194, 191 }, { 193, 194 }, { 194, 198 }, { 185, 196 }, { 196, 198 }, { 198, 185 },
            { 195, 196 }, { 185, 197 }, { 197, 193 }, { 198, 199 }, { 197, 198 }, { 198, 193 },
            { 195, 198 }, { 195, 199 } };
        testOnGraph(edges);
    }

    /**
     * Random not planar graph on 200 vertices
     */
    @Test
    public void testPlanarity35()
    {
        int[][] edges = new int[][] { { 0, 170 }, { 1, 19 }, { 2, 55 }, { 3, 195 }, { 4, 140 },
            { 5, 157 }, { 6, 35 }, { 7, 87 }, { 8, 103 }, { 9, 138 }, { 10, 99 }, { 11, 26 },
            { 12, 23 }, { 13, 138 }, { 14, 72 }, { 15, 75 }, { 16, 179 }, { 17, 121 }, { 18, 195 },
            { 19, 156 }, { 20, 118 }, { 21, 167 }, { 22, 188 }, { 23, 94 }, { 24, 182 },
            { 25, 139 }, { 26, 13 }, { 27, 25 }, { 28, 138 }, { 29, 51 }, { 30, 189 }, { 31, 13 },
            { 32, 145 }, { 33, 163 }, { 34, 72 }, { 35, 199 }, { 36, 69 }, { 37, 119 }, { 38, 196 },
            { 39, 35 }, { 40, 79 }, { 41, 55 }, { 42, 14 }, { 43, 195 }, { 44, 188 }, { 45, 118 },
            { 46, 51 }, { 47, 105 }, { 48, 132 }, { 49, 191 }, { 50, 139 }, { 51, 15 }, { 52, 123 },
            { 53, 157 }, { 54, 15 }, { 55, 64 }, { 56, 137 }, { 57, 12 }, { 58, 179 }, { 59, 138 },
            { 60, 164 }, { 61, 137 }, { 62, 174 }, { 63, 27 }, { 64, 61 }, { 65, 139 }, { 66, 63 },
            { 67, 133 }, { 68, 8 }, { 69, 21 }, { 70, 138 }, { 71, 48 }, { 72, 77 }, { 73, 82 },
            { 74, 104 }, { 75, 170 }, { 76, 155 }, { 77, 195 }, { 78, 5 }, { 79, 69 }, { 80, 60 },
            { 81, 127 }, { 82, 34 }, { 83, 117 }, { 84, 164 }, { 85, 0 }, { 86, 66 }, { 87, 148 },
            { 88, 35 }, { 89, 166 }, { 90, 138 }, { 91, 76 }, { 92, 130 }, { 93, 82 }, { 94, 26 },
            { 95, 121 }, { 96, 106 }, { 97, 185 }, { 98, 152 }, { 99, 169 }, { 100, 7 },
            { 101, 59 }, { 102, 180 }, { 103, 184 }, { 104, 196 }, { 105, 103 }, { 106, 93 },
            { 107, 124 }, { 108, 1 }, { 109, 173 }, { 110, 66 }, { 111, 130 }, { 112, 47 },
            { 113, 7 }, { 114, 157 }, { 115, 35 }, { 116, 187 }, { 117, 69 }, { 118, 66 },
            { 119, 174 }, { 120, 73 }, { 121, 75 }, { 122, 118 }, { 123, 3 }, { 124, 40 },
            { 125, 122 }, { 126, 171 }, { 127, 137 }, { 128, 19 }, { 129, 176 }, { 130, 175 },
            { 131, 189 }, { 132, 104 }, { 133, 92 }, { 134, 123 }, { 135, 169 }, { 136, 57 },
            { 137, 34 }, { 138, 137 }, { 139, 108 }, { 140, 40 }, { 141, 39 }, { 142, 151 },
            { 143, 171 }, { 144, 80 }, { 145, 130 }, { 146, 33 }, { 147, 92 }, { 148, 118 },
            { 149, 183 }, { 150, 155 }, { 151, 26 }, { 152, 191 }, { 153, 17 }, { 154, 27 },
            { 155, 90 }, { 156, 74 }, { 157, 52 }, { 158, 21 }, { 159, 17 }, { 160, 134 },
            { 161, 116 }, { 162, 8 }, { 163, 104 }, { 164, 14 }, { 165, 85 }, { 166, 70 },
            { 167, 69 }, { 168, 105 }, { 169, 72 }, { 170, 73 }, { 171, 159 }, { 172, 119 },
            { 173, 30 }, { 174, 32 }, { 175, 125 }, { 176, 92 }, { 177, 12 }, { 178, 105 },
            { 179, 92 }, { 180, 185 }, { 181, 3 }, { 182, 128 }, { 183, 44 }, { 184, 80 },
            { 185, 67 }, { 186, 46 }, { 187, 5 }, { 188, 173 }, { 189, 108 }, { 190, 77 },
            { 191, 67 }, { 192, 53 }, { 193, 9 }, { 194, 31 }, { 195, 123 }, { 196, 158 },
            { 197, 113 }, { 198, 23 }, { 199, 129 }, { 0, 197 }, { 1, 155 }, { 2, 151 }, { 3, 24 },
            { 4, 127 }, { 5, 85 }, { 6, 72 }, { 7, 85 }, { 8, 23 }, { 9, 169 }, { 10, 80 },
            { 11, 56 }, { 12, 54 }, { 13, 29 }, { 14, 198 }, { 15, 127 }, { 16, 169 }, { 17, 54 },
            { 18, 17 }, { 19, 113 } };
        testOnGraph(edges);
    }

    /**
     * Triangulation of 300 points
     */
    @Test
    public void testPlanarity36()
    {
        int[][] edges = new int[][] { { 1, 0 }, { 0, 3 }, { 3, 1 }, { 0, 2 }, { 2, 5 }, { 5, 0 },
            { 11, 24 }, { 24, 9 }, { 9, 11 }, { 6, 14 }, { 14, 5 }, { 5, 6 }, { 7, 2 }, { 0, 7 },
            { 4, 27 }, { 27, 0 }, { 0, 4 }, { 5, 3 }, { 2, 8 }, { 8, 18 }, { 18, 2 }, { 2, 6 },
            { 1, 10 }, { 7, 8 }, { 123, 4 }, { 18, 6 }, { 0, 21 }, { 21, 7 }, { 9, 3 }, { 5, 9 },
            { 21, 8 }, { 15, 1 }, { 3, 15 }, { 10, 13 }, { 40, 24 }, { 24, 33 }, { 33, 40 },
            { 5, 11 }, { 12, 10 }, { 1, 12 }, { 14, 19 }, { 19, 5 }, { 15, 22 }, { 22, 12 },
            { 12, 15 }, { 29, 43 }, { 43, 46 }, { 46, 29 }, { 5, 17 }, { 17, 11 }, { 12, 20 },
            { 20, 10 }, { 18, 14 }, { 16, 13 }, { 10, 16 }, { 23, 26 }, { 26, 20 }, { 20, 23 },
            { 19, 17 }, { 17, 24 }, { 19, 25 }, { 25, 17 }, { 39, 18 }, { 18, 38 }, { 38, 39 },
            { 3, 22 }, { 21, 18 }, { 26, 10 }, { 26, 29 }, { 29, 10 }, { 14, 31 }, { 31, 19 },
            { 37, 21 }, { 21, 27 }, { 27, 37 }, { 22, 34 }, { 34, 12 }, { 12, 23 }, { 29, 16 },
            { 17, 36 }, { 36, 24 }, { 40, 9 }, { 17, 28 }, { 28, 36 }, { 25, 28 }, { 30, 34 },
            { 22, 30 }, { 41, 43 }, { 29, 41 }, { 31, 25 }, { 42, 21 }, { 37, 42 }, { 3, 30 },
            { 29, 32 }, { 32, 41 }, { 34, 23 }, { 26, 32 }, { 23, 32 }, { 31, 35 }, { 35, 25 },
            { 35, 28 }, { 4, 62 }, { 62, 27 }, { 40, 51 }, { 51, 9 }, { 54, 64 }, { 64, 34 },
            { 34, 54 }, { 51, 3 }, { 42, 18 }, { 34, 32 }, { 31, 44 }, { 44, 35 }, { 36, 33 },
            { 52, 35 }, { 35, 48 }, { 48, 52 }, { 36, 40 }, { 46, 16 }, { 14, 39 }, { 39, 31 },
            { 39, 44 }, { 64, 68 }, { 68, 71 }, { 71, 64 }, { 44, 48 }, { 42, 38 }, { 3, 47 },
            { 47, 30 }, { 42, 53 }, { 53, 38 }, { 45, 34 }, { 30, 45 }, { 46, 13 }, { 52, 28 },
            { 53, 39 }, { 45, 54 }, { 28, 55 }, { 55, 36 }, { 41, 56 }, { 56, 43 }, { 45, 47 },
            { 47, 59 }, { 59, 45 }, { 40, 49 }, { 49, 50 }, { 50, 40 }, { 64, 32 }, { 32, 61 },
            { 61, 41 }, { 53, 44 }, { 36, 49 }, { 37, 60 }, { 60, 42 }, { 50, 51 }, { 53, 48 },
            { 51, 47 }, { 52, 57 }, { 57, 28 }, { 51, 59 }, { 56, 58 }, { 58, 43 }, { 52, 53 },
            { 53, 70 }, { 70, 52 }, { 55, 49 }, { 55, 63 }, { 63, 49 }, { 63, 50 }, { 58, 46 },
            { 63, 67 }, { 67, 50 }, { 60, 75 }, { 75, 53 }, { 53, 60 }, { 57, 86 }, { 86, 55 },
            { 55, 57 }, { 65, 46 }, { 58, 65 }, { 59, 54 }, { 59, 68 }, { 68, 54 }, { 61, 69 },
            { 69, 72 }, { 72, 61 }, { 61, 56 }, { 60, 62 }, { 62, 78 }, { 78, 60 }, { 27, 60 },
            { 70, 57 }, { 66, 77 }, { 77, 65 }, { 65, 66 }, { 67, 51 }, { 67, 85 }, { 85, 51 },
            { 4, 101 }, { 101, 62 }, { 64, 61 }, { 64, 74 }, { 74, 69 }, { 69, 64 }, { 72, 56 },
            { 77, 46 }, { 58, 66 }, { 85, 59 }, { 97, 70 }, { 70, 79 }, { 79, 97 }, { 92, 57 },
            { 70, 92 }, { 72, 58 }, { 76, 77 }, { 77, 73 }, { 73, 76 }, { 85, 87 }, { 87, 59 },
            { 70, 75 }, { 75, 79 }, { 71, 74 }, { 172, 46 }, { 77, 172 }, { 72, 80 }, { 80, 58 },
            { 68, 81 }, { 81, 71 }, { 73, 66 }, { 58, 73 }, { 80, 73 }, { 74, 80 }, { 72, 74 },
            { 96, 78 }, { 78, 95 }, { 95, 96 }, { 86, 63 }, { 78, 75 }, { 74, 83 }, { 83, 80 },
            { 82, 71 }, { 81, 82 }, { 86, 67 }, { 80, 88 }, { 88, 73 }, { 62, 99 }, { 99, 78 },
            { 83, 88 }, { 94, 104 }, { 104, 105 }, { 105, 94 }, { 82, 74 }, { 75, 89 }, { 89, 79 },
            { 82, 83 }, { 87, 68 }, { 88, 76 }, { 87, 81 }, { 84, 77 }, { 76, 84 }, { 94, 84 },
            { 84, 88 }, { 88, 94 }, { 81, 91 }, { 91, 82 }, { 93, 102 }, { 102, 87 }, { 87, 93 },
            { 67, 90 }, { 90, 85 }, { 86, 90 }, { 91, 83 }, { 98, 88 }, { 83, 98 }, { 92, 86 },
            { 90, 112 }, { 112, 85 }, { 89, 97 }, { 85, 93 }, { 96, 75 }, { 91, 98 }, { 105, 84 },
            { 92, 97 }, { 97, 118 }, { 118, 92 }, { 118, 86 }, { 102, 81 }, { 96, 89 }, { 102, 91 },
            { 91, 113 }, { 113, 98 }, { 100, 109 }, { 109, 96 }, { 96, 100 }, { 86, 111 },
            { 111, 90 }, { 99, 95 }, { 90, 103 }, { 103, 112 }, { 99, 100 }, { 100, 95 },
            { 98, 104 }, { 104, 88 }, { 101, 106 }, { 106, 107 }, { 107, 101 }, { 110, 96 },
            { 109, 110 }, { 108, 99 }, { 99, 101 }, { 101, 108 }, { 107, 108 }, { 102, 113 },
            { 115, 77 }, { 84, 115 }, { 112, 93 }, { 123, 101 }, { 111, 116 }, { 116, 103 },
            { 103, 111 }, { 108, 100 }, { 105, 115 }, { 120, 105 }, { 104, 120 }, { 110, 89 },
            { 108, 109 }, { 110, 119 }, { 119, 89 }, { 123, 106 }, { 119, 97 }, { 106, 121 },
            { 121, 107 }, { 121, 108 }, { 112, 102 }, { 121, 109 }, { 125, 112 }, { 112, 114 },
            { 114, 125 }, { 136, 140 }, { 140, 120 }, { 120, 136 }, { 113, 117 }, { 117, 98 },
            { 118, 111 }, { 117, 104 }, { 140, 172 }, { 172, 115 }, { 115, 140 }, { 125, 131 },
            { 131, 112 }, { 103, 114 }, { 103, 122 }, { 122, 114 }, { 120, 115 }, { 131, 102 },
            { 116, 122 }, { 117, 128 }, { 128, 104 }, { 119, 129 }, { 129, 97 }, { 111, 122 },
            { 118, 138 }, { 138, 111 }, { 119, 126 }, { 126, 129 }, { 130, 121 }, { 121, 124 },
            { 124, 130 }, { 122, 127 }, { 127, 114 }, { 110, 126 }, { 121, 123 }, { 123, 124 },
            { 130, 109 }, { 132, 102 }, { 131, 132 }, { 128, 136 }, { 136, 104 }, { 130, 110 },
            { 129, 118 }, { 144, 159 }, { 159, 132 }, { 132, 144 }, { 113, 128 }, { 111, 135 },
            { 135, 122 }, { 123, 137 }, { 137, 124 }, { 127, 125 }, { 130, 126 }, { 135, 145 },
            { 145, 147 }, { 147, 135 }, { 126, 133 }, { 133, 129 }, { 133, 134 }, { 134, 129 },
            { 134, 118 }, { 130, 141 }, { 141, 126 }, { 181, 123 }, { 132, 113 }, { 137, 139 },
            { 139, 124 }, { 132, 128 }, { 135, 127 }, { 134, 138 }, { 147, 127 }, { 139, 130 },
            { 135, 143 }, { 143, 145 }, { 149, 130 }, { 139, 149 }, { 147, 125 }, { 150, 133 },
            { 133, 142 }, { 142, 150 }, { 138, 135 }, { 141, 146 }, { 146, 126 }, { 138, 143 },
            { 156, 172 }, { 140, 156 }, { 126, 142 }, { 123, 173 }, { 173, 137 }, { 148, 136 },
            { 128, 148 }, { 125, 157 }, { 157, 131 }, { 150, 134 }, { 137, 149 }, { 150, 158 },
            { 158, 134 }, { 162, 164 }, { 164, 136 }, { 136, 162 }, { 131, 144 }, { 146, 142 },
            { 132, 148 }, { 177, 151 }, { 151, 170 }, { 170, 177 }, { 147, 157 }, { 158, 138 },
            { 146, 152 }, { 152, 154 }, { 154, 146 }, { 149, 141 }, { 151, 145 }, { 143, 151 },
            { 149, 160 }, { 160, 141 }, { 148, 162 }, { 153, 158 }, { 158, 170 }, { 170, 153 },
            { 138, 153 }, { 153, 143 }, { 141, 152 }, { 151, 147 }, { 173, 149 }, { 157, 144 },
            { 142, 154 }, { 154, 155 }, { 155, 142 }, { 153, 151 }, { 155, 150 }, { 160, 152 },
            { 155, 163 }, { 163, 150 }, { 160, 174 }, { 174, 152 }, { 157, 161 }, { 161, 144 },
            { 159, 148 }, { 161, 165 }, { 165, 168 }, { 168, 161 }, { 158, 166 }, { 166, 170 },
            { 174, 154 }, { 159, 168 }, { 168, 148 }, { 164, 156 }, { 140, 164 }, { 163, 166 },
            { 166, 150 }, { 154, 163 }, { 161, 159 }, { 173, 160 }, { 169, 188 }, { 188, 164 },
            { 164, 169 }, { 157, 165 }, { 157, 167 }, { 167, 165 }, { 168, 162 }, { 175, 156 },
            { 164, 175 }, { 147, 167 }, { 173, 178 }, { 178, 160 }, { 167, 185 }, { 185, 165 },
            { 176, 154 }, { 174, 176 }, { 168, 187 }, { 187, 162 }, { 177, 147 }, { 162, 169 },
            { 167, 177 }, { 177, 191 }, { 191, 167 }, { 171, 169 }, { 162, 171 }, { 183, 172 },
            { 172, 175 }, { 175, 183 }, { 194, 169 }, { 171, 194 }, { 184, 166 }, { 163, 184 },
            { 163, 176 }, { 176, 184 }, { 165, 179 }, { 179, 168 }, { 187, 171 }, { 179, 180 },
            { 180, 195 }, { 195, 179 }, { 184, 189 }, { 189, 166 }, { 178, 192 }, { 192, 160 },
            { 179, 187 }, { 192, 174 }, { 178, 181 }, { 181, 199 }, { 199, 178 }, { 181, 173 },
            { 174, 184 }, { 197, 217 }, { 217, 183 }, { 183, 197 }, { 180, 182 }, { 182, 195 },
            { 165, 180 }, { 189, 170 }, { 185, 180 }, { 285, 181 }, { 188, 175 }, { 183, 188 },
            { 188, 197 }, { 185, 182 }, { 193, 170 }, { 189, 193 }, { 185, 186 }, { 186, 182 },
            { 192, 203 }, { 203, 174 }, { 186, 222 }, { 222, 182 }, { 170, 190 }, { 190, 177 },
            { 187, 196 }, { 196, 171 }, { 190, 191 }, { 190, 193 }, { 193, 201 }, { 201, 190 },
            { 190, 205 }, { 205, 191 }, { 191, 185 }, { 185, 202 }, { 202, 186 }, { 212, 192 },
            { 192, 199 }, { 199, 212 }, { 195, 187 }, { 206, 188 }, { 188, 194 }, { 194, 206 },
            { 203, 224 }, { 224, 174 }, { 193, 200 }, { 200, 204 }, { 204, 193 }, { 206, 197 },
            { 208, 217 }, { 197, 208 }, { 195, 196 }, { 184, 207 }, { 207, 189 }, { 196, 198 },
            { 198, 171 }, { 189, 200 }, { 198, 194 }, { 202, 222 }, { 198, 216 }, { 216, 194 },
            { 195, 215 }, { 215, 196 }, { 201, 205 }, { 191, 202 }, { 181, 209 }, { 209, 199 },
            { 228, 202 }, { 202, 214 }, { 214, 228 }, { 203, 213 }, { 213, 224 }, { 202, 211 },
            { 211, 214 }, { 206, 208 }, { 204, 201 }, { 220, 189 }, { 207, 220 }, { 204, 210 },
            { 210, 234 }, { 234, 204 }, { 209, 212 }, { 205, 211 }, { 211, 191 }, { 189, 210 },
            { 210, 200 }, { 201, 218 }, { 218, 205 }, { 217, 172 }, { 234, 201 }, { 222, 195 },
            { 218, 211 }, { 203, 212 }, { 212, 213 }, { 181, 247 }, { 247, 209 }, { 215, 198 },
            { 223, 172 }, { 217, 223 }, { 225, 184 }, { 184, 224 }, { 224, 225 }, { 220, 210 },
            { 209, 236 }, { 236, 212 }, { 243, 215 }, { 215, 229 }, { 229, 243 }, { 236, 213 },
            { 216, 206 }, { 218, 221 }, { 221, 211 }, { 216, 219 }, { 219, 206 }, { 221, 214 },
            { 219, 208 }, { 232, 217 }, { 208, 232 }, { 195, 227 }, { 227, 215 }, { 226, 214 },
            { 221, 226 }, { 219, 231 }, { 231, 232 }, { 232, 219 }, { 210, 233 }, { 233, 238 },
            { 238, 210 }, { 220, 233 }, { 222, 227 }, { 228, 240 }, { 240, 249 }, { 249, 228 },
            { 227, 229 }, { 207, 225 }, { 225, 220 }, { 215, 230 }, { 230, 198 }, { 239, 241 },
            { 241, 225 }, { 225, 239 }, { 218, 226 }, { 226, 228 }, { 236, 224 }, { 228, 222 },
            { 236, 252 }, { 252, 224 }, { 230, 216 }, { 235, 242 }, { 242, 246 }, { 246, 235 },
            { 249, 222 }, { 234, 218 }, { 230, 231 }, { 231, 216 }, { 240, 218 }, { 234, 240 },
            { 238, 240 }, { 234, 238 }, { 240, 226 }, { 232, 223 }, { 246, 232 }, { 232, 235 },
            { 243, 230 }, { 230, 250 }, { 250, 231 }, { 237, 241 }, { 241, 245 }, { 245, 237 },
            { 231, 235 }, { 220, 237 }, { 237, 233 }, { 245, 233 }, { 224, 239 }, { 231, 242 },
            { 255, 222 }, { 249, 255 }, { 220, 241 }, { 247, 236 }, { 255, 227 }, { 246, 223 },
            { 245, 253 }, { 253, 233 }, { 247, 248 }, { 248, 236 }, { 253, 259 }, { 259, 233 },
            { 250, 242 }, { 243, 244 }, { 244, 230 }, { 251, 252 }, { 252, 248 }, { 248, 251 },
            { 244, 250 }, { 256, 223 }, { 246, 256 }, { 255, 229 }, { 259, 238 }, { 229, 254 },
            { 254, 243 }, { 242, 256 }, { 252, 258 }, { 258, 224 }, { 258, 239 }, { 229, 262 },
            { 262, 254 }, { 254, 244 }, { 247, 251 }, { 250, 257 }, { 257, 242 }, { 258, 241 },
            { 241, 260 }, { 260, 245 }, { 285, 247 }, { 267, 238 }, { 259, 267 }, { 253, 261 },
            { 261, 259 }, { 267, 240 }, { 251, 263 }, { 263, 252 }, { 254, 257 }, { 257, 244 },
            { 255, 262 }, { 258, 260 }, { 284, 255 }, { 255, 274 }, { 274, 284 }, { 257, 273 },
            { 273, 242 }, { 266, 245 }, { 260, 266 }, { 240, 264 }, { 264, 249 }, { 285, 251 },
            { 269, 281 }, { 281, 266 }, { 266, 269 }, { 249, 274 }, { 266, 253 }, { 263, 258 },
            { 264, 274 }, { 267, 264 }, { 262, 276 }, { 276, 254 }, { 258, 265 }, { 265, 260 },
            { 283, 265 }, { 265, 278 }, { 278, 283 }, { 263, 268 }, { 268, 258 }, { 264, 272 },
            { 272, 275 }, { 275, 264 }, { 276, 257 }, { 266, 261 }, { 285, 263 }, { 281, 261 },
            { 268, 271 }, { 271, 258 }, { 267, 272 }, { 277, 267 }, { 259, 277 }, { 260, 269 },
            { 268, 270 }, { 270, 271 }, { 261, 277 }, { 280, 282 }, { 282, 273 }, { 273, 280 },
            { 271, 265 }, { 263, 270 }, { 271, 278 }, { 279, 280 }, { 280, 276 }, { 276, 279 },
            { 283, 260 }, { 270, 285 }, { 285, 286 }, { 286, 270 }, { 282, 242 }, { 275, 290 },
            { 290, 274 }, { 274, 275 }, { 284, 262 }, { 292, 277 }, { 277, 289 }, { 289, 292 },
            { 282, 256 }, { 280, 257 }, { 281, 277 }, { 281, 289 }, { 292, 267 }, { 283, 269 },
            { 291, 295 }, { 295, 284 }, { 284, 291 }, { 284, 276 }, { 297, 270 }, { 286, 297 },
            { 284, 279 }, { 292, 272 }, { 295, 279 }, { 292, 275 }, { 278, 288 }, { 288, 283 },
            { 283, 293 }, { 293, 269 }, { 295, 280 }, { 271, 287 }, { 287, 278 }, { 270, 287 },
            { 287, 288 }, { 288, 296 }, { 296, 283 }, { 293, 281 }, { 297, 287 }, { 290, 291 },
            { 291, 274 }, { 282, 295 }, { 293, 289 }, { 291, 294 }, { 294, 299 }, { 299, 291 },
            { 289, 298 }, { 298, 299 }, { 299, 289 }, { 275, 294 }, { 294, 290 }, { 292, 294 },
            { 293, 298 }, { 287, 296 }, { 296, 293 }, { 295, 299 }, { 296, 297 }, { 297, 298 },
            { 298, 296 }, { 299, 292 } };
        testOnGraph(edges);
    }

    /**
     * Random not planar graph on 300 vertices
     */
    @Test
    public void testPlanarity37()
    {
        int[][] edges = new int[][] { { 0, 133 }, { 1, 227 }, { 2, 88 }, { 3, 200 }, { 4, 26 },
            { 5, 16 }, { 6, 157 }, { 7, 272 }, { 8, 97 }, { 9, 259 }, { 10, 276 }, { 11, 106 },
            { 12, 239 }, { 13, 156 }, { 14, 18 }, { 15, 292 }, { 16, 9 }, { 17, 171 }, { 18, 152 },
            { 19, 24 }, { 20, 37 }, { 21, 255 }, { 22, 162 }, { 23, 54 }, { 24, 254 }, { 25, 117 },
            { 26, 273 }, { 27, 209 }, { 28, 81 }, { 29, 143 }, { 30, 219 }, { 31, 46 }, { 32, 285 },
            { 33, 19 }, { 34, 263 }, { 35, 48 }, { 36, 225 }, { 37, 254 }, { 38, 138 }, { 39, 251 },
            { 40, 132 }, { 41, 251 }, { 42, 36 }, { 43, 71 }, { 44, 250 }, { 45, 176 }, { 46, 285 },
            { 47, 240 }, { 48, 235 }, { 49, 96 }, { 50, 243 }, { 51, 151 }, { 52, 139 },
            { 53, 207 }, { 54, 84 }, { 55, 128 }, { 56, 296 }, { 57, 81 }, { 58, 60 }, { 59, 116 },
            { 60, 206 }, { 61, 97 }, { 62, 207 }, { 63, 49 }, { 64, 263 }, { 65, 10 }, { 66, 88 },
            { 67, 182 }, { 68, 204 }, { 69, 99 }, { 70, 30 }, { 71, 296 }, { 72, 39 }, { 73, 183 },
            { 74, 236 }, { 75, 299 }, { 76, 200 }, { 77, 280 }, { 78, 220 }, { 79, 216 },
            { 80, 252 }, { 81, 295 }, { 82, 85 }, { 83, 28 }, { 84, 72 }, { 85, 165 }, { 86, 281 },
            { 87, 182 }, { 88, 250 }, { 89, 288 }, { 90, 174 }, { 91, 47 }, { 92, 36 }, { 93, 168 },
            { 94, 153 }, { 95, 231 }, { 96, 274 }, { 97, 217 }, { 98, 77 }, { 99, 3 }, { 100, 123 },
            { 101, 67 }, { 102, 178 }, { 103, 246 }, { 104, 127 }, { 105, 126 }, { 106, 278 },
            { 107, 297 }, { 108, 23 }, { 109, 168 }, { 110, 129 }, { 111, 216 }, { 112, 190 },
            { 113, 95 }, { 114, 129 }, { 115, 275 }, { 116, 260 }, { 117, 176 }, { 118, 74 },
            { 119, 181 }, { 120, 227 }, { 121, 190 }, { 122, 224 }, { 123, 109 }, { 124, 101 },
            { 125, 113 }, { 126, 259 }, { 127, 279 }, { 128, 169 }, { 129, 156 }, { 130, 159 },
            { 131, 245 }, { 132, 34 }, { 133, 34 }, { 134, 132 }, { 135, 95 }, { 136, 225 },
            { 137, 189 }, { 138, 1 }, { 139, 56 }, { 140, 195 }, { 141, 219 }, { 142, 269 },
            { 143, 108 }, { 144, 150 }, { 145, 202 }, { 146, 257 }, { 147, 268 }, { 148, 151 },
            { 149, 227 }, { 150, 106 }, { 151, 86 }, { 152, 126 }, { 153, 128 }, { 154, 226 },
            { 155, 278 }, { 156, 122 }, { 157, 256 }, { 158, 170 }, { 159, 232 }, { 160, 263 },
            { 161, 184 }, { 162, 38 }, { 163, 287 }, { 164, 273 }, { 165, 51 }, { 166, 116 },
            { 167, 195 }, { 168, 139 }, { 169, 294 }, { 170, 111 }, { 171, 53 }, { 172, 261 },
            { 173, 6 }, { 174, 220 }, { 175, 237 }, { 176, 137 }, { 177, 263 }, { 178, 24 },
            { 179, 188 }, { 180, 215 }, { 181, 51 }, { 182, 286 }, { 183, 227 }, { 184, 200 },
            { 185, 205 }, { 186, 85 }, { 187, 247 }, { 188, 274 }, { 189, 60 }, { 190, 149 },
            { 191, 228 }, { 192, 266 }, { 193, 115 }, { 194, 150 }, { 195, 162 }, { 196, 296 },
            { 197, 147 }, { 198, 209 }, { 199, 187 }, { 200, 70 }, { 201, 207 }, { 202, 35 },
            { 203, 155 }, { 204, 296 }, { 205, 12 }, { 206, 33 }, { 207, 293 }, { 208, 196 },
            { 209, 167 }, { 210, 166 }, { 211, 267 }, { 212, 10 }, { 213, 224 }, { 214, 245 },
            { 215, 245 }, { 216, 125 }, { 217, 32 }, { 218, 55 }, { 219, 291 }, { 220, 157 },
            { 221, 90 }, { 222, 77 }, { 223, 185 }, { 224, 84 }, { 225, 183 }, { 226, 23 },
            { 227, 185 }, { 228, 123 }, { 229, 57 }, { 230, 211 }, { 231, 1 }, { 232, 114 },
            { 233, 262 }, { 234, 129 }, { 235, 14 }, { 236, 296 }, { 237, 251 }, { 238, 205 },
            { 239, 172 }, { 240, 106 }, { 241, 148 }, { 242, 183 }, { 243, 284 }, { 244, 299 },
            { 245, 177 }, { 246, 196 }, { 247, 52 }, { 248, 25 }, { 249, 264 }, { 250, 157 },
            { 251, 90 }, { 252, 71 }, { 253, 293 }, { 254, 65 }, { 255, 101 }, { 256, 286 },
            { 257, 115 }, { 258, 65 }, { 259, 225 }, { 260, 135 }, { 261, 122 }, { 262, 131 },
            { 263, 94 }, { 264, 247 }, { 265, 26 }, { 266, 53 }, { 267, 295 }, { 268, 142 },
            { 269, 0 }, { 270, 7 }, { 271, 100 }, { 272, 273 }, { 273, 135 }, { 274, 179 },
            { 275, 239 }, { 276, 271 }, { 277, 11 }, { 278, 130 }, { 279, 180 }, { 280, 52 },
            { 281, 22 }, { 282, 172 }, { 283, 165 }, { 284, 17 }, { 285, 147 }, { 286, 102 },
            { 287, 146 }, { 288, 92 }, { 289, 231 }, { 290, 96 }, { 291, 280 }, { 292, 191 },
            { 293, 142 }, { 294, 125 }, { 295, 9 }, { 296, 172 }, { 297, 52 }, { 298, 263 },
            { 299, 169 }, { 0, 236 }, { 1, 290 }, { 2, 4 }, { 3, 168 }, { 4, 63 }, { 5, 201 },
            { 6, 86 }, { 7, 176 }, { 8, 81 }, { 9, 102 }, { 10, 28 }, { 11, 101 }, { 12, 209 },
            { 13, 255 }, { 14, 170 }, { 15, 36 }, { 16, 222 }, { 17, 77 }, { 18, 36 }, { 19, 17 },
            { 20, 14 }, { 21, 79 }, { 22, 240 }, { 23, 245 }, { 24, 12 }, { 25, 208 }, { 26, 108 },
            { 27, 4 }, { 28, 238 }, { 29, 26 } };
        testOnGraph(edges);
    }
}
