Algorithmic Solutions > LEDA > LEDA Guide > Graphs and Related Data Types > Planar Maps

Planar Maps

It is often useful to visualize the relations represented by a graph to understand them better or to discover new properties. To visualize the relations we need to draw graphs. The nodes are usually drawn as circles or boxes and the edges as lines connecting the nodes.

The data type planar_map represents a planar drawing of a planar graph. A graph is called planar if it can be drawn without edge crossings.

A Planar Map is a bidirected graph and for every node v the cyclic ordering of the edges out of v corresponds to the ordering of the edges around v in the drawing. Nodes and edges are of type item.

A crossing-free drawing of graph in the plane partitions the plane into connected regions, called faces of the drawing. We can associate information with the faces of a Planar Map using Face Arrays and Face Maps .

Example of how to use planar maps


  • All operations performed on a Planar Map are save, that is, the result is still a Planar Map (in contrast to a Graph representing a planar map).


  • not all operations possible for graphs are available for Planar Maps.

Remark: Originally, only the data type planar_map could represent planar maps, but this is in some situations unsatisfactory. It is, for example, not possible to add an arbitrary edge to a planar_map. This is, on the other hand, possible for graphs representing a planar map, although the operation may destroy the face information.


Use Planar Maps if you want to ensure that all operations performed on your planar map result in a planar map. Otherwise use graph to represent planar maps.

Remark: Our experience shows that we rarely use the data type planar_map ourselves.

See also:


Face Arrays

Face Maps

Graphs and Related Data Types

Graph Algorithms

GraphWin for visualizing graphs and graph algorithms

How to Associate Information with nodes and edges

Manual Entries:

Manual Page Planar Maps

LEDA Item Concept

Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH