Hola,
Estuvimos revisando el paper originalmente citado en el libro para el cómputo de los "swap edges", y el texto es muy similar.
No aparece mencionada explícitamente la profundidad del árbol generado, aunque mirando el algoritmo (y considerando la definición de "transitive closure"), parece que se puede llegar a lo que se pide.
Saludos,
Eduardo