  We develop a qubit routing algorithm with polynomial classical run time for
the Quantum Approximate Optimization Algorithm (QAOA). The algorithm follows a
two step process. First, it obtains a near-optimal solution, based on Vizing's
theorem for the edge coloring problem, consisting of subsets of the interaction
gates that can be executed in parallel on a fully parallelized all-to-all
connected QPU. Second, it proceeds with greedy application of SWAP gates based
on their net effect on the distance of remaining interaction gates on a
specific hardware connectivity graph. Our algorithm strikes a balance between
optimizing for both the circuit depth and total SWAP gate count. We show that
it improves upon existing state-of-the-art routing algorithms for QAOA circuits
defined on $k$-regular as well as Erd\"os-Renyi problem graphs of sizes up to
$N \leq 400$.
