This documentation is being rewritten. If something looks off, please cross-check with the Boost 1.91.0 Boost.Graph docs and open an issue.

Planar Graphs

A graph is planar if it can be drawn in a plane with no edge crossings. BGL provides a complete pipeline for planarity testing, embedding, and drawing.

Quick decision

I want to…​ Use

Test if a graph is planar

Boyer-Myrvold Planarity Test

Get a proof of non-planarity

boyer_myrvold_planarity_test with Kuratowski subgraph output, then is_kuratowski_subgraph to verify

Draw a planar graph with no crossings

Full pipeline (see below)

Traverse the faces of an embedded graph

Planar Face Traversal

The drawing pipeline

To produce a straight-line drawing (no edge crossings, all edges are line segments), the input must be a maximal planar graph with a planar embedding. BGL provides functions to build up to that step by step:

  1. make_connected — add edges to make the graph connected

  2. make_biconnected_planar — add edges to make it biconnected (preserving planarity)

  3. make_maximal_planar — add edges to make it maximal planar (triangulated)

  4. planar_canonical_ordering — produce a vertex ordering for drawing

  5. chrobak_payne_straight_line_drawing — compute integer coordinates on a (2n-4) x (n-2) grid

  6. is_straight_line_drawing — verify no edges cross

Each step requires a planar embedding, which is produced by the Boyer-Myrvold planarity test.

Key facts

  • A graph with no self-loops or parallel edges is planar iff it has no subgraph that is an expansion of K5 or K3,3 (Kuratowski’s theorem).

  • A planar graph on n vertices has at most 3n-6 edges and 2n-4 faces (Euler’s formula: n + f = e + c + 1).

  • All algorithms in this section run in O(n) time on planar graphs.

Planar embedding

A planar embedding specifies, for each vertex, the clockwise (or counter-clockwise) order of incident edges. It is the central data structure connecting the planarity test to all downstream algorithms. In BGL it is a property map from vertices to sequences of edge descriptors. See PlanarEmbedding concept.

All algorithms

Algorithm What it does

Boyer-Myrvold

Planarity test. Produces embedding or Kuratowski subgraph.

Planar Face Traversal

Visit all faces of an embedded planar graph.

Canonical Ordering

Vertex ordering for straight-line drawing.

Straight Line Drawing

Compute integer coordinates with no crossings.

Is Straight Line Drawing

Verify a drawing has no crossings.

Is Kuratowski Subgraph

Verify a non-planarity certificate.

Make Connected

Add minimal edges to connect the graph.

Make Biconnected Planar

Add edges to make biconnected while preserving planarity.

Make Maximal Planar

Add edges to triangulate while preserving planarity.
Edit this Page