Algorithms for Planar Graphs

A graph is called planar if it can be drawn in the plane without edge crossings. In a drawing of a graph, nodes are identified with points in the plane and edges with lines connecting the corresponding end nodes. The edges are not allowed to cross nodes in the drawing.

A planar embedding represents a class of planar drawings. Given a planar embedding planar drawings of the graph can be easily constructed.

Interesting Fact 1: A famous theorem by Kuratowski states that a graph is planar if and only if it does not contain special subgraphs, called Kuratowski subgraphs. Therefore, to test a graph for planarity it is not necessary to really draw the graph.

Interesting Fact 2: A planar graph G=(V,E) (without parallel edges and selfloops) can have at most 3|V|-6 edges.

LEDA Functions for Planar Graphs

• Planarity Testing
• st-Numbering
• Triangulation a Planar Map
• Coloring the Nodes of a Graph with Five Colors
• Independent Sets

See also:

Graph Algorithms

Graphs and Related Data Types

Manual Entries: