Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Member Functions | Private Member Functions | Private Attributes | List of all members
ogdf::BoothLueker Class Reference
Graph Algorithms » Planarity and Planarization » Planarity Testing and Embedding

Booth-Lueker planarity test. More...

#include <ogdf/planarity/BoothLueker.h>

+ Inheritance diagram for ogdf::BoothLueker:

Public Member Functions

 BoothLueker ()
 
 ~BoothLueker ()
 
virtual bool isPlanar (const Graph &G) override
 Returns true, if G is planar, false otherwise. More...
 
virtual bool isPlanarDestructive (Graph &G) override
 Returns true, if G is planar, false otherwise. More...
 
virtual bool planarEmbed (Graph &G) override
 Returns true, if G is planar, false otherwise. If true, G contains a planar embedding. More...
 
virtual bool planarEmbedPlanarGraph (Graph &G) override
 Returns true, if G is planar, false otherwise. If true, G contains a planar embedding. More...
 
- Public Member Functions inherited from ogdf::PlanarityModule
 PlanarityModule ()
 
virtual ~PlanarityModule ()
 

Private Member Functions

bool doEmbed (Graph &G, NodeArray< int > &numbering, EdgeArray< edge > &backTableEdges, EdgeArray< edge > &forwardTableEdges)
 Performs a planarity test on a biconnected component of G and embedds it planar. More...
 
bool doTest (Graph &G, NodeArray< int > &numbering)
 Performs a planarity test on a biconnected component of G. More...
 
void entireEmbed (Graph &G, NodeArray< SListPure< adjEntry >> &entireEmbedding, NodeArray< SListIterator< adjEntry >> &adjMarker, NodeArray< bool > &mark, node v)
 
bool preparation (Graph &G, bool embed)
 Prepares the planarity test and the planar embedding. More...
 
void prepareParallelEdges (Graph &G)
 

Private Attributes

EdgeArray< bool > m_isParallel
 
int m_parallelCount
 
EdgeArray< ListPure< edge > > m_parallelEdges
 

Detailed Description

Booth-Lueker planarity test.

This class implements the linear-time planarity test proposed by Booth and Luecker, based on PQ-trees.
This class is deprecated! You will usually want to use the more modern/faster/versatile linear-time planarity test by Boyer and Myrvold instead, implemented in the class BoyerMyrvold. Generally, it is suggested to use the direct function calls isPlanar and planarEmbed in extended_graph_alg.h (which in turn use BoyerMyrvold).

Definition at line 52 of file BoothLueker.h.

Constructor & Destructor Documentation

◆ BoothLueker()

ogdf::BoothLueker::BoothLueker ( )
inline

Definition at line 54 of file BoothLueker.h.

◆ ~BoothLueker()

ogdf::BoothLueker::~BoothLueker ( )
inline

Definition at line 56 of file BoothLueker.h.

Member Function Documentation

◆ doEmbed()

bool ogdf::BoothLueker::doEmbed ( Graph &  G,
NodeArray< int > &  numbering,
EdgeArray< edge > &  backTableEdges,
EdgeArray< edge > &  forwardTableEdges 
)
private

Performs a planarity test on a biconnected component of G and embedds it planar.

numbering contains an st-numbering of the component.

◆ doTest()

bool ogdf::BoothLueker::doTest ( Graph &  G,
NodeArray< int > &  numbering 
)
private

Performs a planarity test on a biconnected component of G.

numbering contains an st-numbering of the component.

◆ entireEmbed()

void ogdf::BoothLueker::entireEmbed ( Graph &  G,
NodeArray< SListPure< adjEntry >> &  entireEmbedding,
NodeArray< SListIterator< adjEntry >> &  adjMarker,
NodeArray< bool > &  mark,
node  v 
)
private

◆ isPlanar()

virtual bool ogdf::BoothLueker::isPlanar ( const Graph &  G)
overridevirtual

Returns true, if G is planar, false otherwise.

Implements ogdf::PlanarityModule.

◆ isPlanarDestructive()

virtual bool ogdf::BoothLueker::isPlanarDestructive ( Graph &  G)
overridevirtual

Returns true, if G is planar, false otherwise.

Implements ogdf::PlanarityModule.

◆ planarEmbed()

virtual bool ogdf::BoothLueker::planarEmbed ( Graph &  G)
inlineoverridevirtual

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

Implements ogdf::PlanarityModule.

Definition at line 65 of file BoothLueker.h.

◆ planarEmbedPlanarGraph()

virtual bool ogdf::BoothLueker::planarEmbedPlanarGraph ( Graph &  G)
inlineoverridevirtual

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

For BoothLueker, this procedure is exactly the same as planarEmbed. (See PlanarityModule or BoyerMyrvold for the rationale of this function's existence.

Implements ogdf::PlanarityModule.

Definition at line 72 of file BoothLueker.h.

◆ preparation()

bool ogdf::BoothLueker::preparation ( Graph &  G,
bool  embed 
)
private

Prepares the planarity test and the planar embedding.

◆ prepareParallelEdges()

void ogdf::BoothLueker::prepareParallelEdges ( Graph &  G)
private

Member Data Documentation

◆ m_isParallel

EdgeArray<bool> ogdf::BoothLueker::m_isParallel
private

Definition at line 103 of file BoothLueker.h.

◆ m_parallelCount

int ogdf::BoothLueker::m_parallelCount
private

Definition at line 104 of file BoothLueker.h.

◆ m_parallelEdges

EdgeArray<ListPure<edge> > ogdf::BoothLueker::m_parallelEdges
private

Definition at line 102 of file BoothLueker.h.

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