Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ogdf::UpwardPlanarity Class Reference

Upward planarity testing and embedding. More...

#include <ogdf/upward/UpwardPlanarity.h>

Static Public Member Functions

General digraphs
static bool isUpwardPlanar (Graph &G)
 Tests whether graph G is upward planar (using satisfiability).
 
static bool embedUpwardPlanar (Graph &G, adjEntry &externalToItsRight)
 Tests whether graph G is upward planar and embeds the graph by a upward planar embedding if possible (using satisfiability).
 
Biconnected digraphs
static bool isUpwardPlanar_embedded (const Graph &G)
 Tests whether a biconnected graph G is upward planarly embedded.
 
static bool isUpwardPlanar_embedded (const Graph &G, List< adjEntry > &possibleExternalFaces)
 Tests whether a biconnected graph G is upward planarly embedded and computes the set of possible external faces.
 
Triconnected digraphs
static bool isUpwardPlanar_triconnected (const Graph &G)
 Tests whether the triconnected digraph G is upward planar.
 
static bool upwardPlanarEmbed_triconnected (Graph &G)
 Upward planarly embeds the triconnected digraph G.
 
Single-source digraphs
static bool isUpwardPlanar_singleSource (const Graph &G)
 Tests whether the single-source digraph G is upward planar.
 
static bool upwardPlanarEmbed_singleSource (Graph &G)
 Upward planarly embeds the single-source digraph G.
 
static bool upwardPlanarAugment_singleSource (Graph &G)
 Tests whether single-source digraph G is upward planar, and if yes augments it to a planar st-digraph.
 
static bool upwardPlanarAugment_singleSource (Graph &G, node &superSink, SList< edge > &augmentedEdges)
 Tests whether single-source digraph G is upward planar, and if yes augments it to a planar st-digraph.
 
static bool isUpwardPlanar_singleSource_embedded (const ConstCombinatorialEmbedding &E, SList< face > &externalFaces)
 Tests whether the embedding E of a single-source digraph is upward planar.
 
static bool upwardPlanarAugment_singleSource_embedded (Graph &G, node &superSink, SList< edge > &augmentedEdges)
 Tests if single-source digraph G is upward planarly embedded and augments it to a planar st-digraph.
 

Detailed Description

Upward planarity testing and embedding.

This class provides various static functions for upward planarity testing and embedding. These functions perform different tasks (testing, embedding, augmenting) and pose different restrictions on the input graph (general, biconnected, single source).

We use a strict naming scheme to make it clear what the functions are doing and which restrictions they have. The prefix of the function name denotes the task:

  • isUpwardPlanar: Tests if the input graph is upward planar.
  • upwardPlanarEmbed: First tests if the input graph is upward planar, and if yes upward planarly embeds it.
  • upwardPlanarAugment: Adds additional edges to the input graph such that the graph remains upward planar and fulfills a special property like single source.

The suffix of the function name (if present) describes additional restrictions:

  • singleSource: The input graph has exactly one source (but possibly several sinks).
  • seriesParallel: The input graph is a series-parallel graph.

Some of the functions take a combinatorial embedding (e.g., given by the order in the adjacency lists) as input and test this given embedding. These functions are appended by _embedded.

Definition at line 72 of file UpwardPlanarity.h.

Member Function Documentation

◆ embedUpwardPlanar()

static bool ogdf::UpwardPlanarity::embedUpwardPlanar ( Graph G,
adjEntry externalToItsRight 
)
static

Tests whether graph G is upward planar and embeds the graph by a upward planar embedding if possible (using satisfiability).

Parameters
Gis the input graph to be embedded if it allows an upward planar embedding.
externalToItsRightindicates the external face (on its right side)
Returns
true if G is upward planar, false otherwise.

◆ isUpwardPlanar()

static bool ogdf::UpwardPlanarity::isUpwardPlanar ( Graph G)
static

Tests whether graph G is upward planar (using satisfiability).

Parameters
Gis the input graph to be tested.
Returns
true if G is upward planar, false otherwise.

◆ isUpwardPlanar_embedded() [1/2]

static bool ogdf::UpwardPlanarity::isUpwardPlanar_embedded ( const Graph G)
static

Tests whether a biconnected graph G is upward planarly embedded.

The fixed embedding of G is given by the order of G's adjacency lists.

Parameters
Gis the input graph to be tested.
Returns
true if G is upward planarly embedded, false otherwise.

◆ isUpwardPlanar_embedded() [2/2]

static bool ogdf::UpwardPlanarity::isUpwardPlanar_embedded ( const Graph G,
List< adjEntry > &  possibleExternalFaces 
)
static

Tests whether a biconnected graph G is upward planarly embedded and computes the set of possible external faces.

◆ isUpwardPlanar_singleSource()

static bool ogdf::UpwardPlanarity::isUpwardPlanar_singleSource ( const Graph G)
static

Tests whether the single-source digraph G is upward planar.

Remarks
If G is not single-source the function returns false.
Parameters
Gis the (single-source) input digraph.
Returns
true if G was single-source and upward planar, false otherwise.

◆ isUpwardPlanar_singleSource_embedded()

static bool ogdf::UpwardPlanarity::isUpwardPlanar_singleSource_embedded ( const ConstCombinatorialEmbedding E,
SList< face > &  externalFaces 
)
static

Tests whether the embedding E of a single-source digraph is upward planar.

Parameters
Eis the given combinatorial embedding to be tested.
externalFacesis assigned the list of possible external faces such that E is upward planar.
Returns
true if E is upward planar, false otherwise.

◆ isUpwardPlanar_triconnected()

static bool ogdf::UpwardPlanarity::isUpwardPlanar_triconnected ( const Graph G)
static

Tests whether the triconnected digraph G is upward planar.

Remarks
If G is not triconnected the function returns false.
Parameters
Gis the (triconnected) input digraph.
Returns
true if G was triconnected and upward planar, false otherwise.

◆ upwardPlanarAugment_singleSource() [1/2]

static bool ogdf::UpwardPlanarity::upwardPlanarAugment_singleSource ( Graph G)
static

Tests whether single-source digraph G is upward planar, and if yes augments it to a planar st-digraph.

Remarks
If G is not single-source the function returns false.

If G is upward planar, this method adds a super sink node t and adds further edges such that the resulting digraph is a planar st-digraph.

Parameters
Gis the input digraph which gets augmented.
Returns
true if G is single-source and upward planar, false otherwise.

◆ upwardPlanarAugment_singleSource() [2/2]

static bool ogdf::UpwardPlanarity::upwardPlanarAugment_singleSource ( Graph G,
node superSink,
SList< edge > &  augmentedEdges 
)
static

Tests whether single-source digraph G is upward planar, and if yes augments it to a planar st-digraph.

Remarks
If G is not single-source the function returns false.

If G is upward planar, this method adds a super sink node superSink and adds further edges such that the resulting digraph is a planar st-digraph.

Parameters
Gis the input digraph which gets augmented.
superSinkis assigned the inserted super sink node.
augmentedEdgesis assigned the list of inserted edges.
Returns
true if G is single-source and upward planar, false otherwise.

◆ upwardPlanarAugment_singleSource_embedded()

static bool ogdf::UpwardPlanarity::upwardPlanarAugment_singleSource_embedded ( Graph G,
node superSink,
SList< edge > &  augmentedEdges 
)
static

Tests if single-source digraph G is upward planarly embedded and augments it to a planar st-digraph.

Parameters
Gis the embedded input graph.
superSinkis assigned the added super sink.
augmentedEdgesis assigned the list of added edges.
Returns
true if G is upward planarly embedded (in this case G is also augmented by adding a super sink and additional edges), false otherwise.

◆ upwardPlanarEmbed_singleSource()

static bool ogdf::UpwardPlanarity::upwardPlanarEmbed_singleSource ( Graph G)
static

Upward planarly embeds the single-source digraph G.

Remarks
If G is not single-source the function returns false.
Parameters
Gis the (single-source) input digraph.
Returns
true if G was single-source and upward planar, false otherwise.

◆ upwardPlanarEmbed_triconnected()

static bool ogdf::UpwardPlanarity::upwardPlanarEmbed_triconnected ( Graph G)
static

Upward planarly embeds the triconnected digraph G.

Remarks
If G is not triconnected the function returns false.
Parameters
Gis the (triconnected) input digraph.
Returns
true if G was triconnected and upward planar, false otherwise.

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