← Back to Math Roadmap

Placement & Positioning — Quadratic Force-Directed Placement

How EDA tools decide WHERE each component sits on the PCB before routing — building the Laplacian matrix from a netlist, solving quadratic systems, and legalizing positions on a grid. Complete Python implementation included.

What is Component Placement?

▼
Before we can route any traces, we need to decide WHERE each component sits on the board. This is the placement problem, and it's the step that happens BEFORE autorouting. Imagine you're arranging furniture in a room — you want pieces that interact frequently to be close together, while spreading everything out so nothing overlaps. Placement algorithms do exactly this for circuit components.

The industry-standard approach is called Quadratic Force-Directed Placement. Think of every connection between two components as a spring pulling them together. Components that are strongly connected (critical signals, like the timing capacitor to the NE555 chip) get stiffer springs (higher weights). Components on the board edges (connectors, mounting holes) are anchored — they can't move. The algorithm finds the equilibrium position where all spring forces balance — the minimum-energy configuration.

Mathematically, this is pure linear algebra expressed through graph theory. The netlist (which pin connects to which) becomes a weighted adjacency matrix, which transforms into a graph Laplacian, which produces a linear system Ax = b that we solve with standard numerical methods. And the beautiful part: X and Y coordinates are independent — we solve two separate linear systems of the same structure.

1. From Netlist to Graph — Building the Connectivity Matrix

▼
A netlist is just a list of connections: "Component A pin 3 connects to Component B pin 7." For placement, we abstract away individual pins and work at the component level. Each component becomes a single point (its centroid), and each connection becomes an edge with a weight. If component A has three pins connecting to component B, that becomes a single edge with weight = 3.

Let's formalize this. We have n components: some are FIXED (connectors at the board edge, mounting holes) and some are MOVABLE (chips, resistors, capacitors we need to place). The connections between them form a weighted undirected graph G = (V, E).

Define the connectivity matrix C (n × n):
- C[i][j] = connection weight between component i and component j (0 if not connected)
- C[i][i] = 0 (no self-connections)
- C is symmetric: C[i][j] = C[j][i]

This is identical to a weighted adjacency matrix from graph theory — just with a different name.
Connectivity matrix entry C[i][j]. Sum all nets connecting components i and j, each weighted by w_net. For critical signals (timing, noise-sensitive), increase w_net to pull harder.

2. The Graph Laplacian — The Engine of Placement

▼
From the connectivity matrix C, we build the graph Laplacian matrix A, also called the stiffness matrix in engineering (it has the same structure as a spring-mass system). This is where the magic happens — the Laplacian encodes ALL the connectivity information into a single matrix that, when solved, gives optimal positions.

The Laplacian A is defined as:
- Diagonal entries A[i][i] = sum of all connection weights FROM component i. This is the degree of node i in the weighted graph. If R1 connects to CON1 with weight 1 and to U1 with weight 1, then A[R1][R1] = 2.
- Off-diagonal entries A[i][j] = -C[i][j] for i ≠ j. This is the negative of the connection weight. The negative sign is crucial — it's what creates the "pulling" force toward other components.

The Laplacian has a beautiful property: every row sums to zero because the diagonal equals the sum of all off-diagonals (with their negative signs): A[i][i] + Σ_{j≠i} A[i][j] = 0. This zero-sum property is what makes the force-directed model physically meaningful — forces balance in equilibrium.

For a spring system, the Laplacian is identical to the stiffness matrix in finite element analysis. When you solve A * x = b, you're finding the displacement x where the internal spring forces balance the external boundary conditions b. This equivalence between graph theory, circuit placement, and structural engineering is one of the most elegant cross-domain connections in applied math.
Graph Laplacian from connectivity matrix. Diagonal = weighted degree (total pull on component i). Off-diagonal = -weight (negative = attractive force). Row sums always equal zero.

3. Quadratic Cost Function — Why Least Squares?

▼
Why do we minimize the square of distances rather than absolute distances? This is the key insight of analytical placement.

If component is at and component is at , the wire length (Euclidean) would be . Minimizing the sum of Euclidean distances is a difficult nonlinear problem with no closed-form solution.

But if we minimize the squared distance — — the problem becomes quadratic and separable. The X and Y dimensions decouple completely:
Total wire-length cost. Each connection (i,j) with weight c_ij contributes its squared Euclidean distance.
The cost separates into independent X and Y components! This means we solve the same linear system twice — once for X coordinates and once for Y.
The X-cost and Y-cost are independent — we solve two separate problems with the same matrix structure! This is the fundamental trick of quadratic placement. The trade-off: squared distance over-penalizes long wires (a wire of length 10 contributes 100 to the squared cost vs 10 to Euclidean). But the computational simplicity makes it worth it, and a follow-up nonlinear refinement step can correct for this.
In matrix form: the quadratic cost expands to x^T A x where A is the graph Laplacian. Taking the derivative and setting to zero gives A x = b — a linear system!

4. Solving the Linear System — Separating Fixed and Movable

▼
We now have the quadratic cost function Φ(x) = x^T A x. To find the minimum, take the derivative with respect to x and set to zero: ∂Φ/∂x = 2A x = 0, which gives A x = 0. But this would place ALL components at the origin — useless! The fixed components (connectors) must stay where they are.

We split our components into two groups: F (fixed, with known positions) and M (movable, positions to solve for). Partition the Laplacian A accordingly into four blocks:
Partitioned Laplacian. FF = fixed-fixed interactions. FM/MF = fixed-movable coupling. MM = movable-movable interactions — this is the submatrix we solve.
The system A · x = 0 becomes a pair of matrix equations:
The upper equation involves fixed-fixed and fixed-movable. The lower equation is the one we solve for x_M — the movable positions.
We already know x_F (the fixed positions of CON1 and CON2). We want to find x_M. From the second equation above, isolate the x_M term:
This is the fundamental linear system of quadratic placement! The right-hand side b = −A_MF × x_F is the force vector — it encodes how the fixed components pull on the movable ones through the spring network.
The right-hand side is the force vector — it encodes how the fixed components "pull" on the movable ones through the spring network. Solving this system gives the equilibrium positions where all spring forces balance.

Key insight: is symmetric positive definite (as long as each movable component is connected to at least one fixed component, directly or through a chain). This guarantees a unique solution and lets us use fast Cholesky decomposition or conjugate gradient solvers. The same matrix is used for both X and Y dimensions — we solve two linear systems with different right-hand sides ( and ), a perfect use case for LU decomposition (factor once, solve twice).

5. Worked Example — NE555 Timer Circuit Placement

▼
The Netlist
Let's place a realistic circuit: an NE555 timer driving an LED, with filtering and protection components. We have 6 components — 2 fixed (board connectors) and 4 movable (chip, resistor, capacitor, LED).

FIXED COMPONENTS (F):
- CON1 (Input Connector): anchored at (x=0, y=50)
- CON2 (Output Connector): anchored at (x=120, y=50)

MOVABLE COMPONENTS (M) — positions to solve:
- R1 (Pull-up Resistor, 10kΩ)
- U1 (NE555 Timer IC)
- LED1 (Output Indicator)
- C1 (Filtering Capacitor, 10µF)

NETLIST WITH WEIGHTS:
- CON1 → R1 (weight = 1.0) — input signal path
- R1 → U1 (weight = 1.0) — resistor feeds pin 7 (discharge) of NE555
- U1 → LED1 (weight = 1.0) — NE555 pin 3 (output) drives the LED
- LED1 → CON2 (weight = 1.0) — LED output to connector
- C1 → U1 (weight = 1.5) — timing capacitor to NE555 pin 5 (control voltage). Higher weight because this capacitor is critical for timing stability — any extra wire length adds parasitic inductance that distorts the waveform.

This forms a chain (CON1→R1→U1→LED1→CON2) plus a branch (C1→U1). The chain creates a natural left-to-right placement, and the capacitor's higher weight pulls it close to U1.
Step 1: Assign Indices and Build C (Connectivity Matrix)
Assign each component an index:
- 0: CON1 (FIXED)
- 1: CON2 (FIXED)
- 2: R1 (MOVABLE)
- 3: U1 (MOVABLE)
- 4: LED1 (MOVABLE)
- 5: C1 (MOVABLE)

Build the 6×6 connectivity matrix C by filling in the weights for each connection pair. Remember: C[i][j] = C[j][i] (symmetric), and C[i][i] = 0.

C[0][2] = C[2][0] = 1.0 (CON1 ↔ R1)
C[2][3] = C[3][2] = 1.0 (R1 ↔ U1)
C[3][4] = C[4][3] = 1.0 (U1 ↔ LED1)
C[4][1] = C[1][4] = 1.0 (LED1 ↔ CON2)
C[5][3] = C[3][5] = 1.5 (C1 ↔ U1, higher weight!)

All other entries = 0.
Step 2: Build the Laplacian A
The Laplacian A is built from C: diagonal = row sum of C, off-diagonal = -C[i][j].

A[0][0] = C[0][2] = 1.0 → Row 0 (CON1) has one connection to R1
A[0][2] = -C[0][2] = -1.0 → Negative weight to R1

A[1][1] = C[1][4] = 1.0 → Row 1 (CON2) has one connection to LED1
A[1][4] = -C[1][4] = -1.0

A[2][2] = C[2][0] + C[2][3] = 1.0 + 1.0 = 2.0 → R1 connects to CON1 and U1
A[2][0] = -1.0, A[2][3] = -1.0

A[3][3] = C[3][2] + C[3][4] + C[3][5] = 1.0 + 1.0 + 1.5 = 3.5 → U1 connects to R1, LED1, C1
A[3][2] = -1.0, A[3][4] = -1.0, A[3][5] = -1.5

A[4][4] = C[4][3] + C[4][1] = 1.0 + 1.0 = 2.0
A[4][3] = -1.0, A[4][1] = -1.0

A[5][5] = C[5][3] = 1.5
A[5][3] = -1.5

Verify: each row sums to zero. Row 3: 3.5 + (-1) + (-1) + (-1.5) = 0 ✓
Step 3: Extract A_MM and A_MF, Build the Linear System
Separate into FIXED rows/cols {0, 1} and MOVABLE rows/cols {2, 3, 4, 5}.

A_MM (4×4) — movable-movable interactions:
Row 2 (R1):   [ 2.0, -1.0,  0.0,  0.0]
Row 3 (U1):   [-1.0,  3.5, -1.0, -1.5]
Row 4 (LED1): [ 0.0, -1.0,  2.0,  0.0]
Row 5 (C1):   [ 0.0, -1.5,  0.0,  1.5]


A_MF (4×2) — movable-fixed coupling:
Row 2 (R1):   [-1.0,  0.0]    (CON1 pulls R1)
Row 3 (U1):   [ 0.0,  0.0]    (U1 not directly connected to any fixed comp)
Row 4 (LED1): [ 0.0, -1.0]    (CON2 pulls LED1)
Row 5 (C1):   [ 0.0,  0.0]    (C1 not directly connected to any fixed comp)


Fixed positions: ,

Right-hand side :
-
-
-
-

(same calculation with ):
-
-
-
-

So and . The nonzero entries tell us: CON2 pulls LED1 to x=120 (via the chain), and CON1 pulls R1 to y=50.
Step 4: Solve the Linear System by Hand
Solve by substitution (Cholesky would do this automatically for large systems):

Equation 1 (R1):
Equation 4 (C1):
Equation 3 (LED1):
Equation 2 (U1):

Substitute and into Equation 2:




Plug into Equation 3:




Back-substitute:
30
90
60

For Y (same matrix, different b): all y coordinates solve to 50 because is symmetric — the anchors at pull everything to center. This makes sense: all components align on a horizontal line CON1—R1—U1—LED1—CON2.
Continuous optimal positions. Notice U1 and C1 collide at (60,50) — they need grid legalization! CON1 at (0,50) and CON2 at (120,50) are fixed anchors.

🎬 Interactive Placement Simulation — Watch the Springs Pull!

▼
Click Simulate to watch the spring-force algorithm in action. Components start at random positions and the spring network pulls them to their optimal equilibrium. The red solid line shows the critical C1→U1 connection (weight 1.5). Dashed blue lines are normal connections (weight 1.0). After settling, grid-snapped positions are displayed.
Phase 1: SolvePhase 2: Grid SnapDone
VCC (+5V)GND (0V)w=1.5 criticalw=1.0 signal

💻 Complete Python Implementation — Quadratic Placement Solver

▼

6. Grid Legalization — From Continuous Math to Discrete PCB

▼
The quadratic solver gives us continuous optimal positions — floating-point coordinates like (30.0, 50.0). But real PCBs use a discrete grid (typically 0.1mm or 5-mil steps in imperial units). Components must snap to this grid so traces can align cleanly.

Simple grid snapping rounds each coordinate to the nearest grid point: x_grid = round(x / GRID) × GRID. This works for isolated components but creates collisions when two components snap to the same cell. In our example, U1 and C1 both solve to (60, 50). After snapping to a 10-unit grid, they'd both land at (60, 50) — a collision!

Collision resolution strategies, from simple to sophisticated:
1. Shift-to-right: push the second component one grid cell to the right (or down). Simple, fast, used in this example.
2. Spiral search: expand in a spiral from the target position until an empty cell is found. Minimizes displacement from optimal.
3. Force-directed refinement: after snapping, run a few iterations of pair-wise repulsion to spread colliding components.
4. Linear complementarity: formulate legalization as a constrained optimization — minimize displacement while enforcing non-overlap (used in industrial tools like RePlAce).

In our solution, C1 moves from (60, 50) → (70, 50) — shifted right by one grid cell to avoid colliding with U1 at (60, 50). The capacitance-critical connection (weight 1.5) still pulls C1 close to U1 — it's just 10 units away instead of 0. The mathematical equilibrium is preserved as much as possible while respecting physical constraints.

After placement, the next step is autorouting — connecting all the placed components with copper traces that avoid obstacles and each other.

📍 Final Legalized PCB Layout

▼
The completed placement with all components in their legalized grid positions. U1 at (60,50), C1 shifted to (70,50) to resolve the collision. Blue dashed lines = normal connections. Red solid line = critical C1→U1 connection (weight 1.5). Toggle the grid overlay.

💡 Key Insights — Why Quadratic Placement is Industry Standard

▼
💡 Key Insights — Why Quadratic Placement is Industry Standard
1. The Laplacian encodes the entire placement problem. One matrix captures ALL connectivity information, and solving Ax=b gives the optimal configuration. This is spectral graph theory in action — the Laplacian's properties (symmetry, positive definiteness, zero row sums) directly map to physical spring forces.

2. X and Y are independent. This separation is the secret sauce — we solve one matrix twice instead of one giant coupled system. For a circuit with 10,000 movable components, we solve two 10,000×10,000 systems instead of one 20,000×20,000 system. That's 4× less memory and 8× faster computation.

3. Weights are the designer's voice. Higher weights on critical nets (like the 1.5× on C1→U1) directly control placement priority. Timing-critical clocks, noise-sensitive analog signals, and high-current power traces all get elevated weights — the math naturally reflects engineering intent.

4. The fixed components are anchors. Without fixed components, the optimal solution places everything at the origin (A×0 = 0). The fixed components (connectors, mounting holes) provide essential boundary conditions — they "pull" the network into a meaningful configuration.

5. Quadratic is the starting point, not the endpoint. Industrial tools use quadratic placement as phase one, then apply nonlinear refinement (Kraftwerk, RePlAce) that minimizes actual wire length (not squared), followed by detailed legalization, and finally routing. The pipeline is: Place → Legalize → Route — each step builds on the previous.

6. Same math, different domain. The Laplacian appears in heat diffusion (∂u/∂t = −L u), random walks, spectral clustering, image segmentation, and structural engineering. Understanding it in one domain unlocks all others — this is the power of applied mathematics.