1. A computer system that routes connections in an integrated circuit (IC) chip design, comprising: a representation mechanism configured to represent routing resources in the IC chip design as a 3-dimensional (3D) grid, which comprises: a static 3D grid comprising static grid lines which do not change while the system routes the connections; and a dynamic 3D grid comprising a 2D dynamic grid plane which spans across a full span of the static 3D grid along a first direction and multiple metal layers along a second direction, and wherein the 2D dynamic grid plane is created for routing a connection that includes pins which are not located on a static grid line, wherein the 2D dynamic grid plane is removed after the connection is routed; and a search engine configured to search for a path in the 3D grid between a first set of vertices and a second set of vertices.