Module org.jgrapht.core
Package org.jgrapht.alg.interfaces

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 Details

    • 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

    • getEmbedding

      PlanarityTestingAlgorithm.Embedding<V,E> getEmbedding()
      Computes combinatorial embedding of the input graph. This method will return a valid result only if the graph is planar. For more information on the combinatorial embedding, see PlanarityTestingAlgorithm.Embedding
      Returns:
      combinatorial embedding of the input graph

    • 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