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