Module org.jgrapht.core
Package org.jgrapht.alg.planar

Class BoyerMyrvoldPlanarityInspector<V,E>

java.lang.Object
org.jgrapht.alg.planar.BoyerMyrvoldPlanarityInspector<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
PlanarityTestingAlgorithm<V,E>
public class BoyerMyrvoldPlanarityInspector<V,E> extends Object implements PlanarityTestingAlgorithm<V,E>
An implementation of the Boyer-Myrvold planarity testing algorithm. This class determines whether an input graph is planar or not. If the graph is planar, the algorithm provides a combinatorial embedding of the graph, which is represented as a clockwise ordering of the edges of the graph. Otherwise, the algorithm provides a Kuratowski subgraph as a certificate. Both embedding of the graph and Kuratowski subdivision are computed lazily, meaning that the call to the isPlanar() does spend time only on the planarity testing. All of the operations of this algorithm (testing, embedding and Kuratowski subgraph extraction) run in linear time.

A planar graph is a graph, which can be drawn in two-dimensional space without any of its edges crossing. According to the Kuratowski theorem, a graph is planar if and only if it doesn't contain a subdivision of the $K_{3,3}$ or $K_{5}$ graphs.

The Boyer-Myrvold planarity testing algorithm was originally described in: Boyer, John amp; Myrvold, Wendy. (2004). On the Cutting Edge: Simplified O(n) Planarity by Edge Addition. J. Graph Algorithms Appl.. 8. 241-273. 10.7155/jgaa.00091. . We refer to this paper for the complete description of the Boyer-Myrvold algorithm

Author:
Timofey Chudakov

  • Constructor Details

    • BoyerMyrvoldPlanarityInspector

      public BoyerMyrvoldPlanarityInspector(Graph<V,E> graph)
      Creates new instance of the planarity testing algorithm for the graph. The input graph can't be null.
      Parameters:
      graph - the graph to test the planarity of

  • Method Details

    • isPlanar

      public 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 PlanarityTestingAlgorithm.getEmbedding(). Otherwise, a Kuratowski subdivision is provided after the call to the PlanarityTestingAlgorithm.getKuratowskiSubdivision().

      Only the first call to this method does the actual computation, all subsequent calls only return the previously computed value.

      Specified by:
      isPlanar in interface PlanarityTestingAlgorithm<V,E>
      Returns:
      true if the graph is planar, false otherwise

    • getEmbedding

      public 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

      Only the first call to this method does the actual computation, all subsequent calls only return the previously computed value.

      Specified by:
      getEmbedding in interface PlanarityTestingAlgorithm<V,E>
      Returns:
      combinatorial embedding of the input graph

    • getKuratowskiSubdivision

      public 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.

      Only the first call to this method does the actual computation, all subsequent calls only return the previously computed value.

      Specified by:
      getKuratowskiSubdivision in interface PlanarityTestingAlgorithm<V,E>
      Returns:
      a Kuratowski subdivision from the graph