Class LeftRightPlanarityCheck¶

Nested Relationships¶

Inheritance Relationships¶

Class Documentation¶

class LeftRightPlanarityCheck : public NetworKit::Algorithm¶

Public Functions

inline LeftRightPlanarityCheck(const Graph &G)¶

Implements the left-right planarity test as described in citation. This algorithm determines whether a graph is planar, i.e., whether it can be drawn on a plane without any edges crossing. For an overview of planar graphs, refer to: https://en.wikipedia.org/wiki/Planar_graph

The algorithm achieves (almost) linear runtime complexity. The only non-linear component arises from sorting the nodes of the depth-first search tree.

Parameters:

G – The input graph to test for planarity. The graph should be undirected.

Throws:

std::runtime_error – if graph is not an undirected graph

virtual void run() override¶

Executes the left-right planarity test on the input graph. This method performs all necessary computations to determine whether the graph is planar and prepares the result for retrieval via the isPlanar() method.

inline bool isPlanar() const¶

Returns whether the input graph is planar. The result is only valid after the run() method has been called.

Throws:

std::runtime_error – if called before run() has been executed.

Returns:

True if the graph is planar, false otherwise.