In 2000, T. Uno and M. Yagiura published an algorithm that computes all the
common intervals of two given permutations of length
time. Our paper first presents a decomposition approach to obtain a compact encoding for common intervals of
permutations. Then, we revisit T. Uno and M. Yagiura’s algorithm to yield a linear time algorithm for finding this encoding. Besides, we adapt the algorithm to obtain a linear time modular decomposition of an undirected graph, and thereby propose a formal invariant-based proof for all these algorithms.