Planar Graph Checker
Decide planarity for a graph of up to twelve vertices with Euler's bound and an exhaustive K5/K3,3 subdivision search, with a witness.
Planar Graph Checker
Decide planarity for a graph of up to twelve vertices with Euler's bound and an exhaustive K5/K3,3 subdivision search, with a witness.
How this page computes
The page decides whether a simple graph can be drawn in the plane without crossing edges. It applies Euler's bound to every component first, then searches exhaustively for a subdivision of K5 or K3,3.
On K3,3 it prints non-planar with the two sides {A, B, C} and {X, Y, Z} and the nine internally disjoint paths. On a cube it prints planar, with the Euler bound and the number of search steps that support the answer.
The search is exponential, so the page caps the graph at twelve vertices and the search at a stated step budget. Beyond either, it refuses by name instead of calling the graph planar without a proof.
The calculation runs entirely in this browser tab; nothing is uploaded.
A graph is planar when it can be drawn with no crossing edges. The page answers with a proof, not a guess: Euler's bound rules out a graph that is too dense, and an exhaustive search looks for the K5 or K3,3 subdivision Kuratowski's theorem forbids.
For K3,3 it prints the two sides and all nine paths, which is the witness. For a planar graph it prints that no such subdivision exists, which — because the search is exhaustive — is what makes the word planar honest.
How to use Planar Graph Checker
Type one edge per line, two node names. Weights are accepted and ignored, and repeated edges are collapsed.
Press Run. Read the verdict first, then the witness: an Euler inequality, or the branch vertices and disjoint paths of a subdivision.
If the graph has more than twelve vertices or the search passes its step budget, the page refuses and says which limit was hit.
How the method works
Euler's formula gives m ≤ 3n − 6 for a simple planar graph with n ≥ 3 vertices in a component. Breaking that inequality is a complete non-planarity proof, and the page prints the two numbers.
When Euler's bound passes, density alone cannot decide. Kuratowski's theorem says a graph is planar exactly when it has no subdivision of K5 or K3,3, so the page tries every candidate branch set and every packing of internally disjoint paths. A completed search that finds none is the planarity proof.
What to Expect
Best for
- A planarity verdict for a graph of up to twelve vertices
- A witness for a non-planar graph
- Checking that a drawing with no crossings is possible
Not ideal for
- A graph above twelve vertices, which the page refuses by name
- A multigraph or a graph with loops
- A drawing, which this page does not produce
What this tool keeps
- Every node name and edge exactly as typed
What may need cleanup
- Nothing: the verdict and its witness are final
Common errors
- A self-loop is refused as not part of a simple graph
- More than twelve vertices is refused with the cap
- A search that exhausts its step budget is refused, not called planar
Example use cases
- Check that K3,3 is non-planar
- Check that a cube graph is planar
- Find the K5 subdivision in a dense graph
Sample input
K3,3: A-X, A-Y, A-Z, B-X, B-Y, B-Z, C-X, C-Y, C-Z
Sample output
non-planar: a subdivision of K3,3 with sides {A, B, C} and {X, Y, Z}, and the nine disjoint paths
Who this is for
- Students meeting planar graphs
- Readers checking a graph before drawing it
Frequently asked questions
Why twelve vertices?
The subdivision search tries every branch set and every path packing, which grows exponentially. Twelve is the largest size that stays responsive in a browser tab, and above it the page refuses rather than pretending to a verdict.
What is a subdivision?
A graph obtained from K5 or K3,3 by replacing edges with paths. It has the same crossing structure, so it is equally non-planar, and Kuratowski's theorem says every non-planar graph contains one.
Is a completed search really a proof?
Yes for this grammar. The page enumerates every simple path between each candidate pair and every combination of internally disjoint paths, so finding none across all branch sets means no subdivision exists. The printed step count is the size of that search.
Build custom tools for your store
Join the SDK program to create useful ecommerce utilities for your store.