What is a planar graph?

A planar graph is one that can be drawn on a flat plane so that no two edges cross each other anywhere except at shared endpoints.

What is Kuratowski's theorem?

It states that a graph is non-planar if and only if it contains a subdivision of K₅ or K₃,₃ — meaning one of these two graphs, or a version of it with extra vertices inserted along its edges, appears as a subgraph.

What are K₅ and K₃,₃?

K₅ is the complete graph on 5 vertices (every pair connected). K₃,₃ is the complete bipartite graph on two groups of 3 vertices each, with every vertex in one group connected to every vertex in the other — both are the smallest non-planar graphs.

What does the E ≤ 3V − 6 condition mean?

For any planar graph with at least 3 vertices, the number of edges can never exceed 3V − 6 — a direct consequence of Euler's formula for planar graphs (V − E + F = 2). Exceeding this bound proves non-planarity instantly.

Why is the bound tighter for bipartite graphs?

Bipartite planar graphs can't have any triangular faces (3-cycles require an odd cycle, impossible in a bipartite graph), which forces a stricter edge bound of E ≤ 2V − 4.

Why does this checker only search for K₅/K₃,₃ up to 8 vertices?

Searching for a literal K₅ or K₃,₃ subgraph requires checking combinations of 5 or 6 vertices out of the graph, which grows quickly — 8 vertices keeps that search comfortably fast while catching the classic small non-planar examples.

Why isn't 'inconclusive' the same as 'planar'?

This checker only searches for K₅/K₃,₃ as literal subgraphs, not subdivisions (where extra vertices are inserted along the forbidden graph's edges) or minors — a graph could still be non-planar in a way this simplified search doesn't catch, so 'inconclusive' means 'no violation found,' not 'proven planar.'

Where is graph planarity used in real life?

It's fundamental to circuit board design (avoiding crossing traces on a single layer), map and network diagram layout, and graph drawing algorithms that aim for readable, crossing-free visualizations.

Planar Graph Checker — Test Whether a Graph Can Be Drawn Without Crossings

Our Planar Graph Checker tests whether a graph could potentially be drawn on a plane with no edges crossing, applying the necessary edge-count condition (E ≤ 3V − 6, tightened to E ≤ 2V − 4 for bipartite graphs) and, for graphs of 8 or fewer vertices, an explicit search for a K₅ or K₃,₃ subgraph — either of which definitively proves non-planarity by Kuratowski's theorem.

Quick Answer

Enter your graph as an edge list to check the necessary edge-count condition and search for forbidden K₅/K₃,₃ subgraphs — a strong but not fully exhaustive planarity check.

Edges (comma-separated)

Enter edges as NodeA-NodeB, e.g. A-B, A-C, A-D, B-C, B-D, C-D.

How to Use the Planar Graph Checker — Kuratowski-Style Test Online

1
Enter your graph as a comma-separated edge list, e.g. A-B, A-C, A-D, B-C, B-D, C-D.
2
Click 'Calculate' to check the necessary conditions and search for forbidden subgraphs.
3
Review the verdict — 'definitely non-planar' or 'likely planar (inconclusive)' — and the reasoning steps.

Why Use Planar Graph Checker — Kuratowski-Style Test Online?

A graph is planar if it can be drawn on a flat plane with no two edges crossing. Kuratowski's theorem gives an exact characterization: a graph is non-planar if and only if it contains a subdivision of K₅ (the complete graph on 5 vertices) or K₃,₃ (the complete bipartite graph on two groups of 3). Fully detecting subdivisions or minors of these graphs requires sophisticated algorithms (like Boyer-Myrvold) well beyond what a client-side calculator can run instantly — so this tool takes a transparently scoped approach instead: it always checks the necessary edge-count bound (a quick, exact way to rule out many non-planar graphs), and for small graphs (8 or fewer vertices) it additionally searches directly for K₅ or K₃,₃ appearing as literal subgraphs. Finding either proves non-planarity conclusively; not finding one is a strong hint of planarity but not a complete proof, since it won't catch subdivided (edge-expanded) copies of these forbidden graphs.

Frequently Asked Questions

Related Tools

Graph Degree Sequence Validator — Erdős–Gallai Theorem Online

Check whether a sequence of numbers is a valid (graphical) degree sequence using the Erdős–Gallai theorem. Free calculator with step-by-step verification.

Graph Coloring Calculator — Welsh-Powell Algorithm Online

Color a graph's vertices so no two connected nodes share a color, using the greedy Welsh-Powell algorithm. Free calculator with a simple edge-list input.

Adjacency Matrix Calculator — Build a Graph Matrix Online

Build and display the adjacency matrix of a graph from a simple edge-list input, along with its degree sequence. Free calculator, weighted or unweighted.