Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::PlanarityModule Class Referenceabstract

Module for planarity testing and planar embeddings. More...

#include <ogdf/planarity/PlanarityModule.h>

+ Inheritance diagram for ogdf::PlanarityModule:

Public Member Functions

 PlanarityModule ()
 
virtual ~PlanarityModule ()
 
virtual bool isPlanar (const Graph &G)=0
 Returns true, if G is planar, false otherwise. More...
 
virtual bool isPlanarDestructive (Graph &G)=0
 Returns true, if G is planar, false otherwise. In the graph is non-planar, the graph may be arbitrariliy changed after the call. More...
 
virtual bool planarEmbed (Graph &G)=0
 Returns true, if G is planar, false otherwise. If true, G contains a planar embedding. More...
 
virtual bool planarEmbedPlanarGraph (Graph &G)=0
 Constructs a planar embedding of G. G has to be planar! More...
 

Detailed Description

Module for planarity testing and planar embeddings.

This is a module defining functions to test planarity of graphs, and to embed planar graphs (i.e., find a rotation scheme of the edges around their incident vertices defining a plane graph).

Use this module only if you want to be able to (later on) decide which planarity test to use. If you simply want to test planarity or to embed a graph, use the simpler/preferred method: the direct function calls in extended_graph_alg.h (ogdf::isPlanar, ogdf::planarEmbed, ogdf::planarEmbedPlanarGraph), which use the most efficient BoyerMyrvold algorithm.

Definition at line 48 of file PlanarityModule.h.

Constructor & Destructor Documentation

◆ PlanarityModule()

ogdf::PlanarityModule::PlanarityModule ( )
inline

Definition at line 50 of file PlanarityModule.h.

◆ ~PlanarityModule()

virtual ogdf::PlanarityModule::~PlanarityModule ( )
inlinevirtual

Definition at line 52 of file PlanarityModule.h.

Member Function Documentation

◆ isPlanar()

virtual bool ogdf::PlanarityModule::isPlanar ( const Graph G)
pure virtual

Returns true, if G is planar, false otherwise.

Implemented in ogdf::BoyerMyrvold, and ogdf::BoothLueker.

◆ isPlanarDestructive()

virtual bool ogdf::PlanarityModule::isPlanarDestructive ( Graph G)
pure virtual

Returns true, if G is planar, false otherwise. In the graph is non-planar, the graph may be arbitrariliy changed after the call.

This variant may be slightly faster than the default isPlanar

Implemented in ogdf::BoyerMyrvold, and ogdf::BoothLueker.

◆ planarEmbed()

virtual bool ogdf::PlanarityModule::planarEmbed ( Graph G)
pure virtual

Returns true, if G is planar, false otherwise. If true, G contains a planar embedding.

Implemented in ogdf::BoyerMyrvold, and ogdf::BoothLueker.

◆ planarEmbedPlanarGraph()

virtual bool ogdf::PlanarityModule::planarEmbedPlanarGraph ( Graph G)
pure virtual

Constructs a planar embedding of G. G has to be planar!

Returns true if the embedding was successful. Returns false, if the given graph was non-planar (and leaves the graph in an at least partially deleted state)

This routine may be slightly faster than planarEmbed, but requires G to be planar. If G is not planar, the graph will be (partially) destroyed while trying to embed it!

Implemented in ogdf::BoyerMyrvold, and ogdf::BoothLueker.


The documentation for this class was generated from the following file: