Single-layer obstacle-aware routing for substrate interconnections

• Routability-driven constrained Delaunay triangulation can be firstly constructed.
• An efficient flow-based approach is proposed for single-layer obstacle-aware routing.
• The experimental results show that our proposed flow-based approach is efficient.

Due to the limit of available layers and the existence of obstacles in a routing region, single-layer obstacle-aware routing becomes an important issue for substrate interconnections. In this paper, based on the terminals of the given nets, the corner of the rectangular obstacles and the routing plane, routability-driven constrained Delaunay triangulation can be firstly constructed. Furthermore, based on the construction of routability-driven constrained Delaunay triangles, a flow-based approach is proposed to assign the global wires of the given nets in a single layer and an efficient approach is proposed to assign the physical paths of the given nets for single-layer obstacle-aware routing. Compared with the 97.35% routability of the routing nets in the modified combination of Liu׳s topological router [13] and our proposed detailed router for substrate routing with the rectangular obstacles, the experimental results show that our proposed flow-based approach can use less CPU time to obtain the 99.90% routability of the routing nets and shorter total wirelength in a single layer on the average for the tested examples.