y.layout.planar
Class PlanarityTest

java.lang.Object
  y.layout.planar.PlanarityTest

public class PlanarityTest
extends java.lang.Object

Implementation of a planarity test with linear time. This class can be used to test a graph for planarity (isPlanar(Graph), to create a planar embedding of a planar graph (embed(PlanarInformation)) or to find a planar subgraph of a given graph and create an embedding for it (embedPlanarSubgraph(PlanarInformation)).

Constructor Summary

PlanarityTest()
Creates an instance of PlanarityAlgorithm.

Method Summary

boolean	embed(PlanarInformation planar) Creates an embedding of a given graph if it is planar.
boolean	embedPlanarSubgraph(PlanarInformation planar) Runs a planarity test and constructs a valid embedding of the graph.
EdgeList	getNonEmbeddedEdges() Returns a list of edges that were not added to the embedding in a run of embedPlanarSubgraph(PlanarInformation)
boolean	isPlanar(Graph graph) Determines if the a given graph is planar.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PlanarityTest

public PlanarityTest()

Creates an instance of PlanarityAlgorithm. The DFS-tree used for the algorithm is constructed using the given order of nodes and edges in the graph.

Method Detail

isPlanar

public boolean isPlanar(Graph graph)

Determines if the a given graph is planar. Runtime of this test is O(N) where N is the number of nodes.

Parameters:

graph - The graph to test

Returns:

true, if the graph is planar

embed

public boolean embed(PlanarInformation planar)

Creates an embedding of a given graph if it is planar. The result will be saved in the instance of PlanarInformation which is

Parameters:

planar - The PlanarInformation containing the graph to embed.

Returns:

true, if the embedding process was successful.

getNonEmbeddedEdges

public EdgeList getNonEmbeddedEdges()

Returns a list of edges that were not added to the embedding in a run of embedPlanarSubgraph(PlanarInformation)

Returns:

The list of non-embedded edges

embedPlanarSubgraph

public boolean embedPlanarSubgraph(PlanarInformation planar)

Runs a planarity test and constructs a valid embedding of the graph. If the graph is non-planar, some edges are hidden in order to make it planar. A list of hidden edges can be accessed via getNonEmbeddedEdges().

Parameters:

planar - The Graph to test, saved in a PlanarInformation data structure.

Returns:

true, if the graph is planar.