Are all trees planar?

Yes. Their branches can be drawn without crossings, although an arbitrary layout may still cross lines.

Can disconnected graphs be planar?

Yes. Every connected component must be planar, and the components can be drawn separately.

Does nonplanarity prevent useful visualization?

No. It means a faithful plane drawing cannot eliminate every crossing under the usual definition.

AI Glossary / Graphs and symbolic AI / Advanced

Planarity

Definition

Planarity is the property of a graph that allows it to be drawn in a plane without edges crossing, except where they meet at shared endpoints. The property concerns whether a suitable drawing exists, not whether a particular picture already looks crossing-free. Vertices may be repositioned and edges rerouted while preserving the graph's connections. A graph that admits no such drawing is nonplanar.

What it means

A diagram with tangled lines may still represent a planar graph. The tangles could disappear after rearranging the same relationships. Conversely, some connection patterns force crossings in every faithful plane drawing. This is a structural limitation, not necessarily a failure of the drawing software.
Planarity applies to an abstract graph. It does not automatically answer whether wires can be routed around physical obstacles, whether nodes can stay at fixed geographic positions, or whether every directed edge can point upward. Those requirements introduce additional constraints beyond ordinary planarity.

How it works

A planarity test analyzes connectivity and, when successful, can produce a planar embedding. A combinatorial embedding specifies the cyclic order of incident edges around vertices. A separate drawing procedure can convert that structure into coordinates.
NetworkX's check_planarity returns a Boolean result and a certificate. For a planar graph, the certificate is a PlanarEmbedding. For a nonplanar graph, requesting counterexample=True obtains a Kuratowski subgraph as evidence of nonplanarity. Generating this counterexample is optional and costs additional work.
Some edge-count inequalities can quickly prove that a graph is nonplanar. For a simple planar graph with n vertices, where n is at least three, the number of edges m is at most 3n - 6. If the graph is also bipartite, the stronger bound m at most 2n - 4 applies. Passing such a bound is not a complete planarity test.

Three practical examples

A visualization team tests a dependency graph before promising a diagram without crossings. If the graph is nonplanar, it can use visible crossings, filtering, or separate views while clearly showing which relationships each view includes.
A symbolic AI researcher checks whether a graph meets the assumptions of a method designed specifically for planar inputs. The check concerns the graph supplied to the method, rather than the appearance of a published illustration.
An infrastructure planner uses planarity as an initial connectivity question. Even a positive result must be followed by checks involving actual locations, route restrictions, and installation requirements before treating a diagram as a feasible physical design.

Think of it this way

Think of a set of required connections as a puzzle drawn on a sheet. You may move the endpoints and bend the lines, but you cannot erase requirements or turn accidental crossings into new junctions. Planarity asks whether the puzzle has any valid crossing-free solution under those rules.

Worked example

A fictional monitoring design has three controllers, C1 through C3, and four stations, S1 through S4. Every controller must connect directly to every station. There are no links between controllers and no links between stations.
This is a simple bipartite graph: its seven vertices form two groups, and every edge joins the groups. There are 3 × 4 = 12 edges.
The general simple-planar edge bound gives 3 × 7 - 6 = 15. Since 12 is no greater than 15, this check does not rule out planarity. It does not establish it either.
The stronger bipartite-planar bound gives 2 × 7 - 4 = 10. Twelve edges exceed ten, so the graph cannot be planar. No amount of rearranging the seven vertices and rerouting the twelve edges on a plane can satisfy the crossing-free requirement while preserving this graph.
If one required link is removed, eleven edges remain. The graph is still bipartite and still exceeds the bound, so it remains nonplanar. If two links are removed, ten remain; that count now passes the inequality, but passing it alone does not prove the modified graph planar.
A designer could change the requirements or permit physical overpasses. These are changes to the design problem. Neither makes the original abstract graph planar. The calculation establishes a connectivity limitation, not a cost estimate or an installation recommendation.

Illustrative case study

Fictional software firm Elm Bridge prepares an explanation view for an automated scheduling system. Its first prototype repeatedly changes layout settings whenever lines cross. A developer adds a planarity test and discovers that some selected explanation graphs are nonplanar.
The team keeps the complete graph available and adds clearly labeled filtered views for individual scheduling decisions. It checks that filtering does not present omitted relationships as nonexistent. For planar cases, it generates an embedding and then adjusts the rendered layout for readable labels. This fictional case illustrates using a structural test to guide presentation; it does not claim that planar explanations are always easier for users to understand.

Common misconceptions and mistakes

A crossing in one picture does not prove nonplanarity. A different drawing may work.
A low edge count does not guarantee planarity. Edge-count bounds provide necessary conditions under their stated assumptions.
Removing an edge changes the graph, even if the resulting picture becomes simpler.
Adding a junction at a crossing changes connectivity and may change what a network represents.
A combinatorial embedding is not a finished diagram with positions, labels, and adequate spacing.

Business use

Planarity testing helps distinguish avoidable layout clutter from unavoidable crossings in a complete plane representation. Record which graph was tested and how it was constructed from the underlying data. If repeated relationships, self-links, or directed links are simplified for the test, document that interpretation. Preserve the result and any useful certificate alongside the visualization so reviewers can separate structural findings from choices made for presentation.

Check your understanding

How many links are required in the monitoring example?

Answer: Twelve.

Why is the bound of fifteen insufficient to settle that example?

Answer: Passing the general bound does not prove planarity; the bipartite bound of ten rules it out.

Does deleting one link solve the problem?

Answer: No; eleven still exceeds ten.

Related terms

Planar Drawing
planar embedding
graph layout
bipartite graph
Kuratowski subgraph
connected component
Euler's formula
crossing number

Learn next

Build the seven-vertex monitoring graph from its connection list. Predict the result of a planarity test before using software. Then examine a planar graph drawn with unnecessary crossings and explain why the picture and the structural test answer different questions.

Sources

NetworkX, check_planarity: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.planarity.check_planarity.html Oscar Levin, Discrete Mathematics: An Open Introduction, Planar Graphs: https://discrete.openmathbooks.org/dmoi3/sec_planar.html

Previous: Planar Drawing Next: Planning and control layer