Circuit Board Design

Graph Theory · Axiom Academy

REAL WORLD Circuit Board Design How graph theory powers the electronics in your phone, computer, and every modern device The Hidden Graph in Every Device Every electronic device you own—your smartphone, laptop, smartwatch, even your car—contains a printed circuit board (PCB) . These green boards are covered with electronic components that need to be connected together in specific ways. Engineers designing these boards face a fascinating challenge: how do you connect dozens (or thousands) of components when connections can't cross each other on the same layer? This is actually a graph theory problem in disguise! Edges: Connections between points Planar: Can draw with no crossings Vertices: Electronic components Planar: Single-layer board possible Below is a simplified circuit board with 5 components (labeled A-E). Try connecting them to see when crossings occur! Click two components to connect them (or click a connection to remove it) Try adding connections A-E, B-D, and C-E. Watch what happens to the crossings! You've just encountered a fundamental problem in graph theory: graph planarity . A graph is called planar if you can draw it with no edges crossing each other. Some graphs are planar (like a simple square with its diagonals), while others are not (like the complete graph K₅ with 5 vertices all connected to each other). For a single-layer circuit board, what must be true about the component graph?

This is the written version of the interactive lesson above. See the full Graph Theory course.