A graph can look tangled on paper and still be planar. The real question is not whether the current drawing has crossings, but whether some drawing exists with none.
Boyer–Myrvold planarity testing turns that geometric question into a disciplined graph algorithm. It combines depth-first search, incremental edge addition, face structure and obstruction certificates, giving learners a path from visual intuition to professional-grade graph verification.
Quick Read
- Problem: determine whether an undirected graph is planar.
- If planar: produce a combinatorial embedding describing the cyclic order of edges around each vertex.
- If non-planar: practical implementations can isolate a Kuratowski obstruction related to K5 or K3,3.
- Core machinery: depth-first search, back edges, biconnected structure, external faces and incremental edge addition.
- Complexity: Boyer–Myrvold gives linear-time planarity testing under the standard graph model.
- Professional lesson: a boolean answer is weaker than a verifiable certificate.
1. Planar is not the same as “drawn without crossings”
A graph is planar if there exists a drawing in the plane in which edges intersect only at shared endpoints. A badly drawn planar graph may contain many crossings. Planarity is a property of the abstract graph, not of one picture.
This is the first misconception to remove. Before algorithms, give learners the same graph in two different drawings: one crossed, one uncrossed. Ask which property stayed invariant.
2. Two famous non-planar witnesses
Kuratowski’s theorem says a finite graph is planar exactly when it contains no subdivision of K5 or K3,3. These two graphs therefore become canonical obstruction shapes.
- K5: five vertices, every pair connected.
- K3,3: two groups of three vertices, every vertex in one group connected to all three in the other.
At beginner level, these examples build intuition. At professional level, an extracted Kuratowski subgraph can serve as a certificate explaining why a graph failed the planarity test.
3. Euler’s formula gives a cheap filter, not a full test
For a connected planar embedding, Euler’s formula is:
V - E + F = 2It implies useful edge-count bounds such as E≤3V−6 for simple planar graphs with at least three vertices. If a simple graph violates that bound, it is definitely non-planar.
But satisfying the bound does not prove planarity. Use density checks as quick rejection rules, not as substitutes for a complete algorithm.
4. Why depth-first search matters
Boyer–Myrvold begins from a depth-first-search structure. DFS turns an arbitrary graph into a rooted forest with tree edges and back edges. That hierarchy creates an order in which constraints can be propagated and edges can be inserted into a partial embedding.
For learning, trace DFS first. Label discovery order, parent edges and back edges. If learners cannot explain the DFS tree, the later planarity machinery becomes an opaque collection of flags.
5. A combinatorial embedding is not yet a drawing
A planar embedding can be represented by the cyclic order of incident edges around each vertex. This is a combinatorial object: it says which neighbour follows which around a vertex, without yet assigning x-y coordinates.
This distinction is essential in libraries. A planarity test can return an embedding that downstream drawing algorithms then convert into coordinates. “Planar” and “already drawn” are separate jobs.
6. The edge-addition idea
The Boyer–Myrvold method incrementally adds edges while maintaining enough information about the partial embedding to know whether future connections can still be placed without crossings.
The algorithm reasons about externally active structure and walks along the external faces of biconnected components. Instead of testing a huge family of possible drawings, it maintains a compact combinatorial state that records which attachments remain compatible.
The professional insight is general: a geometric existence problem can often be solved by maintaining the right combinatorial invariant rather than constructing every geometry explicitly.
7. Biconnected components reduce ambiguity
Planar embeddings become easier to reason about inside biconnected pieces because articulation points otherwise allow components to rotate or attach in multiple ways. Boyer–Myrvold exploits the way edge additions change biconnected structure.
Before studying the implementation details, make sure articulation vertices and biconnected components are familiar. They explain why local embedding choices can sometimes be handled independently.
8. What a library-level interface looks like
result = planarity_test(G)
if result.is_planar:
embedding = result.embedding
verify_embedding(G, embedding)
else:
obstruction = result.kuratowski_subgraph
verify_obstruction(G, obstruction)That interface is stronger than returning True or False. It gives evidence that can be inspected or independently checked.
9. Why certificates matter
If the graph is planar, a combinatorial embedding can be validated and passed to a drawing routine. If it is non-planar, a Kuratowski subgraph can explain the obstruction.
This is a valuable professional design pattern: when an algorithm makes a structural claim, ask whether it can return a witness that another routine can verify. Certificates make debugging and trust much stronger.
10. Complexity and sparse graphs
The Boyer–Myrvold algorithm is linear-time in the standard planarity-testing setting. Planar graphs themselves are sparse: a simple planar graph with at least three vertices has at most 3V−6 edges. That sparsity helps explain why linear-time graph processing is possible.
Implementation documentation may distinguish the cost of the basic boolean test from the cost of isolating a Kuratowski obstruction on dense non-planar inputs. State what output you request before quoting a complexity bound.
11. Boyer–Myrvold is not the only modern planarity test
Planarity testing has several algorithmic traditions, including Hopcroft–Tarjan, PQ-tree/PC-tree approaches, Left-Right testing and Boyer–Myrvold edge addition. Different libraries choose different implementations.
For example, current NetworkX documentation states that its planarity implementation is based on the Left-Right Planarity Test, while Boost Graph Library exposes Boyer–Myrvold. The correct professional habit is to read the maintained library documentation rather than assume every function named is_planar uses the same internals.
12. Common mistakes
- Judging planarity from one messy drawing.
- Using Euler’s edge bound as if it were sufficient.
- Confusing a planar embedding with final drawing coordinates.
- Ignoring multiedges, self-loops or library-specific graph-model rules.
- Assuming a boolean result is enough when a certificate is available.
- Quoting linear time without saying whether obstruction extraction is included.
- Writing a planarity tester from scratch for production when a maintained library already provides verified machinery.
13. Verification tests
- Trees and cycles, which are planar.
- K4, planar but dense enough to challenge simple intuition.
- K5 and K3,3, both non-planar.
- Subdivisions of K5 and K3,3.
- Disconnected graphs with planar and non-planar components.
- Graphs close to maximal planar density.
- Random small graphs cross-checked against an independent library implementation.
If an embedding is returned, verify its cyclic-order structure and, where appropriate, feed it into a straight-line drawing pipeline and check that no crossings occur.
14. Predict → Run → Investigate → Modify → Make
- Predict: decide whether a crossed drawing can be redrawn without crossings.
- Run: execute a maintained planarity function on K4, K5 and K3,3.
- Investigate: inspect the returned embedding or obstruction certificate.
- Modify: add one edge at a time and predict when planarity will fail.
- Make: build a small teaching tool that displays the certificate rather than only a boolean.
This staged progression follows programming-education work that emphasizes reading, predicting, tracing and modifying before independent construction.
15. Beginner → professional pathway
- Beginner: distinguish planar graphs from crossed drawings and learn K5/K3,3.
- Foundation: use Euler’s formula and edge bounds as necessary checks.
- Intermediate: trace DFS, articulation points and biconnected components.
- Advanced: understand combinatorial embeddings, external-face constraints and obstruction certificates.
- Professional: use maintained planarity libraries, request verifiable witnesses, profile the exact output mode, and keep graph-model assumptions explicit.
Learning Hall Boundary
This article owns Boyer–Myrvold planarity testing as a learning object for DFS-based edge addition, combinatorial embeddings, Kuratowski obstruction certificates and linear-time planarity reasoning. It complements existing graph geometry and traversal material without replacing MindOS, Bolt or Student/Studying Interface canonical jobs. It contains no proprietary eduKateAI architecture, routing, benchmark, score or prompt material.
Sources and further reading
- John Boyer & Wendy Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition, Journal of Graph Algorithms and Applications, 2004.
- Boost Graph Library, Boyer–Myrvold Planarity Testing/Embedding, current documentation.
- NetworkX 3.6.1, Planarity algorithms, for a maintained alternative based on Left-Right testing.
- Magma Handbook, Planar Graphs, implementation-oriented planarity documentation.
- Sentance, Waite & Kallia, Teachers’ Experiences of Using PRIMM to Teach Programming in School.
Professional rule: you understand planarity testing when you can separate abstract planarity from a particular drawing, explain what an embedding certificate represents, and use an obstruction witness to justify a non-planarity result instead of treating the algorithm as a black box.
