Interface PlanarityTestingAlgorithm<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Known Implementing Classes:
    BoyerMyrvoldPlanarityInspector

    public interface PlanarityTestingAlgorithm<V,​E>
    Allows to check the planarity of the graph. A graph is defined to be planar if it can be drawn on a two-dimensional plane without any of its edges crossing.
    Author:
    Timofey Chudakov
    • Method Detail

      • isPlanar

        boolean isPlanar()
        Tests the planarity of the graph. Returns true if the input graph is planar, false otherwise. If this method returns true, the combinatorial embedding of the graph is provided after the call to the getEmbedding(). Otherwise, a Kuratowski subdivision is provided after the call to the getKuratowskiSubdivision().
        Returns:
        true if the graph is planar, false otherwise
      • getKuratowskiSubdivision

        Graph<V,​E> getKuratowskiSubdivision()
        Extracts a Kuratowski subdivision from the graph. The returned value certifies the nonplanarity of the graph. The returned certificate can be verified through the call to the GraphTests.isKuratowskiSubdivision(Graph). This method will return a valid result only if the graph is not planar.
        Returns:
        a Kuratowski subdivision from the graph