Planar Graph Checker
Check whether a graph is planar—drawable without edge crossings—using Kuratowski’s theorem with MiniWebtool’s Planar Graph Checker. It detects K5 and K3,3 subdivisions, verifies Euler’s inequality and highlights the forbidden minor when the graph is non-planar.
For Gemini, paste the copied question into the chat. You can also copy it below.Need help using this tool? Ask AI
View the question
Enter a graph below to test whether it is planar, with Euler's inequality and the K5 or K3,3 subdivision if it is not.
About Planar Graph Checker
The Planar Graph Checker decides whether a simple undirected graph is planar — drawable in the plane without any two edges crossing — and, when the graph fails the test, it finds and visualises the Kuratowski witness: a subdivision of either K₅ (the complete graph on 5 vertices) or K₃,₃ (the complete bipartite graph on 3 + 3 vertices). The tool is built for teaching, competitive programming warm-ups, and quickly sanity-checking small graph constructions.
At a Glance
Planar Graph Checker decides whether a simple undirected graph can be drawn without edge crossings. It tests Euler's inequalities and searches for a K5 or K3,3 subdivision, highlighting the one it finds when the graph is non-planar.
| Feature | What you get | Good for |
|---|---|---|
| Input formats | Enter the graph as an edge list or an adjacency list. Edges are undirected, so A-B and B-A are the same edge. | Typing in graphs from a textbook or a contest problem |
| Size limit | Up to 16 vertices and 60 edges, enough for the Petersen graph, the Möbius-Kantor graph and K7. | Teaching examples and small constructions |
| Euler checks | Applies m ≤ 3n − 6, and m ≤ 2n − 4 for bipartite graphs, to rule out many graphs before searching. | Seeing why a graph has too many edges to be planar |
| Kuratowski witness | Searches for a subdivision of K5 or K3,3 using vertex-disjoint paths and colours it in the drawing, listing the 10 or 9 paths. | Understanding exactly why a graph is non-planar |
| Planar results | For a planar graph the face count F = m − n + 1 + c is shown beside the drawing. | Checking Euler's formula on a concrete graph |
| Graph statistics | Vertex and edge counts, degree sequence, connected components and bipartiteness, plus animated step-by-step reasoning. | Learners following the logic of the verdict |
What Does "Planar" Mean?
A graph G = (V, E) is planar if it can be embedded in the plane so that edges meet only at their shared endpoints — no crossings. Equivalently, G can be drawn on the surface of a sphere without crossings. Planarity is a purely topological property: it does not depend on how you draw the graph, only on whether some crossing-free drawing exists.
Planar graphs show up everywhere — road and utility networks, printed-circuit-board routing, the edge graphs of Platonic solids, and the face structure of polyhedra. Yet many "natural" graphs are stubbornly non-planar: any time you try to connect 3 houses to 3 utilities without crossings, you run into the K₃,₃ barrier.
Kuratowski's Theorem — The Heart of the Checker
Kazimierz Kuratowski proved in 1930 that planarity has a purely combinatorial characterisation:
A subdivision of a graph H is obtained by replacing some edges of H with longer paths whose internal vertices are all new degree-2 vertices. Kuratowski's theorem therefore says that K₅ and K₃,₃ are the only obstructions to planarity — every non-planar graph contains one of them in a "stretched" form.
The Forbidden Graphs
| Graph | Vertices | Edges | Structure | Planar? |
|---|---|---|---|---|
| K₅ | 5 | 10 | Every pair of vertices is joined by an edge (complete graph). | No |
| K₃,₃ | 6 | 9 | Two triples A and B; every a ∈ A is joined to every b ∈ B. | No |
| K₄ | 4 | 6 | Complete graph on 4 vertices. | Yes |
| K₂,₃ | 5 | 6 | Complete bipartite 2 × 3. | Yes |
Euler's Formula and Fast Necessary Conditions
Before running the (relatively expensive) subdivision search, the checker applies two fast necessary conditions derived from Euler's formula: for any connected planar graph drawn in the plane with V vertices, E edges, and F faces (counting the unbounded outer face), we have
Combined with the observation that every face of a simple planar graph has at least 3 edges on its boundary, we get the edge-upper-bound
Any graph violating these inequalities is immediately non-planar, no subdivision search needed. K₅ has m = 10, n = 5 ⇒ 3n − 6 = 9, so 10 > 9 — violates the bound. K₃,₃ has m = 9, n = 6 ⇒ 2n − 4 = 8, so 9 > 8 — violates the bipartite bound.
How the Subdivision Search Works
After the cheap Euler checks, the checker searches for a subdivision directly:
- Quick win — detect K₅ or K₃,₃ as a literal subgraph. If 5 vertices are pairwise adjacent, that's K₅ outright. If 6 vertices split 3 + 3 with all 9 cross-edges present, that's K₃,₃.
- K₅ subdivision search. For each candidate set of 5 "branch" vertices (each with degree ≥ 4 in G), try to find 10 paths — one per pair of branches — that are internally vertex-disjoint (no non-branch vertex appears in more than one path) and avoid using the other branches as internal vertices. A hit proves non-planarity.
- K₃,₃ subdivision search. Pick 6 branches (each with degree ≥ 3) and a 3 + 3 bipartition. Search for 9 cross-pair paths with the same internal-disjointness requirement.
- No witness ⇒ planar. If neither subdivision is found within the size limits, Kuratowski's theorem guarantees the graph is planar.
Finding vertex-disjoint paths is NP-hard in general, so the checker uses a bounded randomised greedy search: each iteration orders the required pairs by difficulty, picks a path for the hardest pair first using a randomised BFS, removes those internal vertices, and continues. If that particular ordering fails, it retries with a shuffled order — up to 40 attempts per branch configuration. On every small graph tested (up to 16 vertices), this suffices to locate a witness whenever one exists.
How to Use This Calculator
- Pick an input format using the tabs at the top: edge list or adjacency list. Either encodes the same graph.
- Enter your graph. The graph is treated as undirected, so
A-BandB-Aare the same edge. - Click Check Planarity. The tool reports a verdict, shows step-by-step reasoning (Euler, bipartite, Kuratowski), and renders the graph.
- For a non-planar graph the visualisation colours the K₅ or K₃,₃ subdivision and lists the 10 (or 9) vertex-disjoint paths. Click a path row to isolate it.
- For a planar graph the face count F = m − n + 1 + c is reported alongside the graph structure.
Worked Example 1 — K₄ is planar
K₄ has n = 4, m = 6. Every graph on ≤ 4 vertices is planar, and indeed K₄ embeds as a triangle with a single vertex inside connected to all three corners. Euler says F = 6 − 4 + 2 = 4 faces: three triangular inner faces plus the outer face.
Worked Example 2 — K₃,₃ is non-planar
K₃,₃ has n = 6, m = 9. It is bipartite, so the bipartite bound applies: m = 9 > 2n − 4 = 8. This alone proves non-planarity. The witness is trivial — K₃,₃ is itself the forbidden subgraph. The tool then highlights the 3 + 3 partition and 9 direct edges.
Worked Example 3 — The Petersen graph
The Petersen graph has n = 10, m = 15, so m ≤ 3n − 6 = 24 and the fast Euler checks pass. Yet it is famously non-planar. The checker locates a K₃,₃ subdivision: pick six vertices from the outer pentagon and inner pentagram so that every cross-pair can be routed through the remaining four vertices by vertex-disjoint paths. The tool draws the witness, making the 1930s geometry tangible.
Applications of Planarity
- VLSI and PCB routing. A single-layer circuit is feasible only if the connection graph is planar; non-planar nets force vias or extra layers.
- Graph drawing and visualisation. Planar graphs admit clear, crossing-free layouts — useful for metro maps, call graphs, and schematic diagrams.
- Algorithm design. Some NP-hard problems get easier on planar graphs: maximum cut becomes solvable in polynomial time, and vertex cover and independent set, while still NP-hard, gain fast approximation schemes. Graph isomorphism (not known to be NP-hard) is also polynomial for planar graphs.
- Graph colouring. The Four Colour Theorem guarantees every planar graph is 4-colourable — a classical result whose statement depends on planarity.
- Combinatorial optimisation. Planar shortest path, max-flow and min-cut all admit specialised fast algorithms.
- Molecular chemistry. Benzene-ring aromatic-hydrocarbon graphs are planar; cage-molecule graphs, such as those of fullerenes, cubane, and dodecahedrane, are also planar.
Frequently Asked Questions
What does planar mean for a graph?
A graph is planar if you can draw it on the plane so that no two edges cross each other except at shared vertices. Equivalently, a graph is planar if and only if it can be drawn on the surface of a sphere without crossings. Trees, cycles, the cube graph, and the Platonic solids are all planar, while K₅ and K₃,₃ are the canonical non-planar examples.
What is Kuratowski's theorem?
Kuratowski's theorem states that a finite graph is planar if and only if it contains no subgraph that is a subdivision of K₅ or K₃,₃. A subdivision is obtained by replacing some edges with longer paths, each through brand-new degree-2 vertices. This gives a concrete combinatorial certificate of non-planarity.
What is the difference between K₅ and K₃,₃?
K₅ has 5 vertices, every pair of which is joined by an edge, for 10 edges total. K₃,₃ has 6 vertices partitioned into two groups of 3, with every vertex in one group connected to every vertex in the other, for 9 edges. Both are the smallest non-planar graphs of their kind, and together they form the forbidden minors for planarity.
How does Euler's inequality help?
Euler's formula V − E + F = 2 for planar connected graphs combined with the fact that every face of a simple planar graph has at least 3 edges yields m ≤ 3n − 6. Any simple graph violating this bound is immediately non-planar. For bipartite planar graphs every face has at least 4 edges, giving the tighter bound m ≤ 2n − 4. The checker applies both as fast rejection rules.
What is the size limit?
The checker handles up to 16 vertices and 60 edges. This covers typical teaching and competition-style graphs including the Petersen graph, the Möbius-Kantor graph, small hypercubes, and the complete graph K₇. Larger graphs require linear-time specialised planarity tests such as Hopcroft-Tarjan or left-right planarity.
How is the witness subdivision drawn?
When the graph is non-planar, the 5 branch vertices of the found K₅ — or the 6 branch vertices of K₃,₃ split into two triples A and B — are highlighted on an inner ring. The 10 (or 9) required internally vertex-disjoint paths are each drawn in a distinct colour so you can trace the K₅ or K₃,₃ topology visually. Vertices and edges that are not part of the subdivision are dimmed.
Further Reading
- Planar graph — Wikipedia
- Kuratowski's theorem — Wikipedia
- Euler characteristic — Wikipedia
- Wagner's theorem (minor version) — Wikipedia
Reference this content, page, or tool as:
"Planar Graph Checker" at https://MiniWebtool.com/planar-graph-checker/ from MiniWebtool, https://MiniWebtool.com/
by miniwebtool team. Updated: Apr 22, 2026
Chat with your favorite AI
For Gemini, paste the copied question into the chat. You can also copy it below.
View the question
Advanced Math Operations:
- Adjacency Matrix Calculator New
- Antilog Calculator
- Beta Function Calculator
- Binomial Coefficient Calculator
- Binomial Probability Distribution Calculator
- Bitwise Calculator Popular
- Boolean Algebra Simplifier Popular
- Central Limit Theorem Calculator
- Chinese Remainder Theorem Calculator
- Combination Calculator
- Complementary Error Function Calculator
- Complex Number Calculator
- Continued Fraction Calculator
- Derangement (Subfactorial) Calculator
- Dijkstra's Shortest Path Calculator
- Entropy Calculator
- Error Function Calculator
- Euler's Totient Function Calculator
- Exponential Decay Calculator
- Exponential Growth Calculator
- Exponential Integral Calculator
- Exponents Calculator
- Extended Euclidean Algorithm Calculator
- Factorial Calculator
- Gamma Function Calculator
- Golden Ratio Calculator
- Graph Coloring Calculator New
- Graph Degree Sequence Validator
- Group Theory Order Calculator New
- Half Life Calculator
- Hamiltonian Path Checker New
- Inclusion-Exclusion Calculator New
- Karnaugh Map (K-Map) Solver New
- Linear Programming Solver New
- Markov Chain Steady State Calculator
- Minimum Spanning Tree Calculator
- Modular Exponentiation Calculator New
- Modular Multiplicative Inverse Calculator
- Negative Binomial Distribution Calculator New
- Network Flow Calculator (Max Flow) New
- Percent Growth Rate Calculator Popular
- Permutation Calculator
- Permutations with Repetition Calculator New
- Pigeonhole Principle Calculator
- Planar Graph Checker New
- Poisson Distribution Calculator
- Polynomial Roots Calculator
- Primitive Root Calculator
- Probability Calculator
- Probability Distribution Calculator
- Proportion Calculator
- Quadratic Formula Calculator
- Ring and Field Calculator New
- Rounding Calculator New
- Scientific Calculator
- Scientific Notation Calculator
- Set Theory Calculator
- Significant Figures Calculator New
- Stable Marriage Problem Solver New
- Stirling Numbers Calculator
- Sum of Cubes Calculator
- Sum of Positive Integers Calculator Popular
- Sum of Squares Calculator
- Topological Sort Calculator New
- Traveling Salesman Solver (TSP) New
- Truth Table Generator
- Venn Diagram Generator (3 Sets)