A routing graph (e.g., a 2.5-D graph) and a method for generating same is
provided for more efficient multiple-layer path searching and routing.
Subgraphs are generated for each layer, and then are combined (e.g.,
through via connections) into a single, multi-layer graph. The resulting
2.5-dimensional graph may be used in VLSI routing, for example, which
commonly includes multiple routing layers in a given design space. Each
subgraph corresponds to a layer of circuitry and includes segments based
on segments from other layers and intersection points of all such
segments. Methods of generating subgraph layers are disclosed.
