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
Public Types
Public Functions
-
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:
trueif 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
embeddingmap 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.
-
inline PlanarDrawing( const Graph & graph )