UpwardPlanarity.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/SList.h>
 
namespace ogdf {
 
 
 
class OGDF_EXPORT UpwardPlanarity {
public:
 
 
    static bool isUpwardPlanar(Graph& G);
 
 
    static bool embedUpwardPlanar(Graph& G, adjEntry& externalToItsRight);
 
#if 0
 
    static int maximalFeasibleUpwardPlanarSubgraph(const Graph &G, GraphCopy &GC);
#endif
 
 
 
 
    static bool isUpwardPlanar_embedded(const Graph& G);
 
    static bool isUpwardPlanar_embedded(const Graph& G, List<adjEntry>& possibleExternalFaces);
 
 
 
 
    static bool isUpwardPlanar_triconnected(const Graph& G);
 
 
    static bool upwardPlanarEmbed_triconnected(Graph& G);
 
 
 
 
 
    static bool isUpwardPlanar_singleSource(const Graph& G);
 
 
    static bool upwardPlanarEmbed_singleSource(Graph& G);
 
 
    static bool upwardPlanarAugment_singleSource(Graph& G);
 
 
    static bool upwardPlanarAugment_singleSource(Graph& G, node& superSink,
            SList<edge>& augmentedEdges);
 
 
 
    static bool isUpwardPlanar_singleSource_embedded(const ConstCombinatorialEmbedding& E,
            SList<face>& externalFaces);
 
 
    static bool upwardPlanarAugment_singleSource_embedded(Graph& G, node& superSink,
            SList<edge>& augmentedEdges);
 
};
 
}