PlanarDrawing

Declared in lemon/planarity.h, in the group Planar Embedding and Drawing; the same class on the Doxygen site.

template< typename Graph >
class PlanarDrawing

Schnyder’s planar drawing algorithm.

The planar drawing algorithm calculates positions for the nodes in the plane. These coordinates satisfy that if the edges are represented with straight lines, then they will not intersect each other.

Scnyder’s algorithm embeds the graph on an (n-2)x(n-2) size grid, i.e. each node will be located in the [0..n-2]x[0..n-2] square. The time complexity of the algorithm is O(n).

See also

PlanarEmbedding

Public Types

typedef dim2::Point< int > Point

The point type for storing coordinates.

typedef Graph::template NodeMap< Point > PointMap

The map type for storing the coordinates of the nodes.

Public Functions

TEMPLATE_GRAPH_TYPEDEFS(Graph)
inline PlanarDrawing( const Graph & graph )

Constructor.

Constructor

Pre:

The graph must be simple, i.e. it should not contain parallel or loop arcs.

inline bool run()

Calculate the node positions.

This function calculates the node positions on the plane.

Returns:

true if the graph is planar.

template< typename EmbeddingMap >
inline void run( const EmbeddingMap & embedding )

Calculate the node positions according to a combinatorical embedding.

This function calculates the node positions on the plane. The given embedding map should contain a valid combinatorical embedding, i.e. a valid cyclic order of the arcs. It can be computed using PlanarEmbedding.

inline Point operator[]( const Node & node ) const

The coordinate of the given node.

This function returns the coordinate of the given node.

inline const PointMap & coords() const

Return the grid embedding in a node map.

This function returns the grid embedding in a node map of dim2::Point< int > coordinates.