PCB_Planarity is a tool for analyzing the planarity of PCB routing graphs. It determines whether a circuit’s connectivity can be routed on a single plane without trace crossings, using planarity analysis grounded in real PCB design constraints and graph theory.
.gif)
- Models PCB connectivity as a graph
- Detects nonplanar subgraphs (e.g. K₃,₃ and K₅)
- Distinguishes fundamentally nonplanar graphs from poor embeddings
- Handles large, realistic circuit topologies
- Bridges graph theory and practical PCB routing
In PCB layout, traces behave like edges in a graph: they must be routed in physical space without crossing when constrained to a single copper layer. Whether this is possible is determined by the structure of the circuit’s connectivity, not by the specific geometry of a layout.
If the connectivity graph is nonplanar, crossings cannot be eliminated through rerouting alone—additional layers or vias are fundamentally required. Canonical nonplanar graphs such as K₃,₃ and K₅ represent these unavoidable routing conflicts. When such structures appear as subgraphs (or minors) of a circuit, single-layer routing is impossible.
This project models circuit connectivity as a graph and explicitly detects these nonplanar cases and configures them into potential arrangements without crossings.
.gif)
This animation shows a K₃,₃ connectivity pattern embedded as traces. Regardless of geometric rearrangement, at least one crossing is unavoidable. This reflects a fundamentally nonplanar routing problem: the trace crossings are not an artifact of poor layout, but of the graph itself.
.gif)
Here, the same logical connectivity is rearranged into a planar embedding. By reconfiguring how edges are routed—without changing the underlying connections—the crossings are eliminated through the additions of new layers and VIAs.
Run the following command:
pip install -r requirements.txtSamuel Bloom, Connor Hoang, Pranav Bonthu, Lukas LittleJohn.