Package org.jgrapht.alg.interfaces
Interface PlanarityTestingAlgorithm<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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
-
-
Nested Class Summary
Nested Classes Modifier and Type Interface Description static interface
PlanarityTestingAlgorithm.Embedding<V,E>
A combinatorial embedding of the graph.static class
PlanarityTestingAlgorithm.EmbeddingImpl<V,E>
Implementation of thePlanarityTestingAlgorithm.Embedding
.
-
Method Summary
All Methods Instance Methods Abstract Methods Modifier and Type Method Description PlanarityTestingAlgorithm.Embedding<V,E>
getEmbedding()
Computes combinatorial embedding of the inputgraph
.Graph<V,E>
getKuratowskiSubdivision()
Extracts a Kuratowski subdivision from thegraph
.boolean
isPlanar()
Tests the planarity of thegraph
.
-
-
-
Method Detail
-
isPlanar
boolean isPlanar()
Tests the planarity of thegraph
. Returns true if the input graph is planar, false otherwise. If this method returns true, the combinatorial embedding of thegraph
is provided after the call to thegetEmbedding()
. Otherwise, a Kuratowski subdivision is provided after the call to thegetKuratowskiSubdivision()
.- Returns:
true
if thegraph
is planar, false otherwise
-
getEmbedding
PlanarityTestingAlgorithm.Embedding<V,E> getEmbedding()
Computes combinatorial embedding of the inputgraph
. This method will return a valid result only if thegraph
is planar. For more information on the combinatorial embedding, seePlanarityTestingAlgorithm.Embedding
- Returns:
- combinatorial embedding of the input
graph
-
getKuratowskiSubdivision
Graph<V,E> getKuratowskiSubdivision()
Extracts a Kuratowski subdivision from thegraph
. The returned value certifies the nonplanarity of the graph. The returned certificate can be verified through the call to theGraphTests.isKuratowskiSubdivision(Graph)
. This method will return a valid result only if thegraph
is not planar.- Returns:
- a Kuratowski subdivision from the
graph
-
-