Planar Graph Checker screenshot

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.

Privacy First
0 Runs
Updated 2026-11-22
Runs in your browser
No sign-up, no upload
Witness, not a guess

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.

Developer program

Build custom tools for your store

Join the SDK program to create useful ecommerce utilities for your store.