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).
#include <lemon/planarity.h>
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 Member Functions | |
PlanarDrawing (const Graph &graph) | |
Constructor. More... | |
bool | run () |
Calculate the node positions. More... | |
template<typename EmbeddingMap > | |
void | run (const EmbeddingMap &embedding) |
Calculate the node positions according to a combinatorical embedding. More... | |
Point | operator[] (const Node &node) const |
The coordinate of the given node. More... | |
const PointMap & | coords () const |
Return the grid embedding in a node map. More... | |
|
inline |
Constructor
|
inline |
This function calculates the node positions on the plane.
true
if the graph is planar.
|
inline |
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 |
This function returns the coordinate of the given node.
|
inline |
This function returns the grid embedding in a node map of dim2::Point<int>
coordinates.