Package org.jgrapht.alg.planar

Class 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 java.lang.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 Detail

      • 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 Detail

      • 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

      • 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