The routing requirements to schedule gates between all possible pairs of qubits depend on the underlying topology where swap operations can be performed. For a linear device, it was shown in [1]} that the most efficient swap network allowing the scheduling of the gates could be executed with maximum parallelization in \(N\)  steps. For a more connected topology, the linear result is still a worst case scenario which can be implemented by defining an arbitrary Hamiltonian path on the device graph.
<FIGURE>