Planar Maps

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

Strengths

• 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).

Disadvantages

• 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.

Tips

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:

Graphs

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