PlanarDrawing< UGraph > Class Template Reference
[Planarity embedding and drawing]

---

Detailed Description

template<typename UGraph>
class lemon::PlanarDrawing< UGraph >

The planar drawing algorithm calculates location for each node in the plane, which coordinates satisfies that if each edge is represented with a straight line then the edges will not intersect each other.

Scnyder's algorithm embeds the graph on (n-2,n-2) size grid, ie. 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>

List of all members.

Public Types
typedef dim2::Point< int >	Point
	The point type for store coordinates.
typedef UGraph::template NodeMap< Point >	PointMap
	The map type for store coordinates.
Public Member Functions
	PlanarDrawing (const UGraph &ugraph)
	Constructor.
bool	run ()
	Calculates the node locations.
template<typename EmbeddingMap >
void	run (const EmbeddingMap &embedding)
	Calculates the node locations according to a combinatorical embedding.
Point	operator[] (const Node &node)
const PointMap &	coords () const
	Returns the grid embedding in a NodeMap.

---

Constructor & Destructor Documentation

PlanarDrawing

(

const UGraph &

ugraph

)

[inline]

Constructor

Precondition:

The ugraph should be simple, ie. loop and parallel edge free.

---

Member Function Documentation

bool run

(

)

[inline]

This function calculates the node locations.

void run

(

const EmbeddingMap &

embedding

)

[inline]

This function calculates the node locations. The embedding parameter should contain a valid combinatorical embedding, ie. a valid cyclic order of the edges.

Point operator[]

(

const Node &

node

)

[inline]

The coordinate of the given node.

const PointMap& coords

(

)

const [inline]

Returns the grid embedding in a NodeMap of dim2::Point<int> .