Introduction
Database
Geometry
1. Euclidean Geometry
2. Boolean Operations
3. Region Queries
Logic
1. BDD
PDKs
Introduction
1. OpenSource PDKs
Library
Introduction
1. Generate Standard-Cells
2. Generate Memory-Macros
I/O & File Formats
File formats
1. LEF/DEF
2. OASIS
3. Verilog
4. Liberty
Physical Synthesis
Introduction
Floorplan
1. Power Routing
2. Well Taps
3. IO Pads
Placement
1. Global Placement
2. Legalization
Buffer & tie-cell insertion
Routing
1. Maze Routing
2. Conflict Resolution
3. 1. Rip-up & Reroute
  2. Negotiation Based Algorithms
4. Hierarchical Routing
5. 1. Global Routing
  2. Resource Estimation
  3. Multilevel Full-Chip Routing
6. Line-Probe Algorithms
Clock-Tree Synthesis
Timing Driven Place & Route
1. Static Timing Analysis
2. 1. Wire Delay Estimation
3. Timing Driven Placement
4. Hold Time Fixing
5. Timing Optimization Strategies
Verification
Netlist Extraction
Netlist Comparison
Design For Test (DFT)
Scan-Chain Insertion
Automated Test-Pattern Generation
Appendix

Line-Probing / Line-Search

Line-probing algorithms search for routes directly based on the geometry. Unlike maze-routers, line-probing does not necessarily need a grid. Hence they can be more memory efficient and faster.

Example algorithms in the literature are:

Hightower's algorithm
Mikami-Tabuchi algorithm

The above algorithms do not guarantee finding the shortest path between two terminals.

Example implementations in LibrEDA

mycelium-router contains an experimental detail router based on a line-search algorithm which guarantees finding the shortest path between two nodes if one exists.