One embodiment of the present invention provides a system that routes connections in an integrated circuit (IC) chip design. The system includes a representation mechanism which is configured to represent routing resources in the IC chip design as a 3-dimensional (3D) grid. This 3D grid further includes: static grid lines which do not change while the system routes the connections; and dynamic grid lines which are created for routing a connection that includes pins which are not located on a static grid line. Note that the dynamic grid lines can be removed after the connection is routed. The system also includes a search engine which is configured to search for a path in the 3D grid between a first set of vertices and a second set of vertices.