Sorting on graphs by adjacent swaps using permutation groups

This paper is a review of sorting on several well-known graphs by adjacent swaps using permutation groups. Given a graph with a line, star, complete, or ring topology having n vertices (numbered from 1 to n), we place n objects (numbered from 1 to n) arbitrarily in such a way that exactly one object is placed on each vertex. A sorting procedure is intended to reach the target object placement in which each object i is placed on vertex i for 1≤i≤n. Now, the problem is to find a minimum-length sequence of adjacent swaps needed to sort the initial arrangement of n objects on n vertices in the graph, which employs a known permutation sorting or permutation decomposition procedure using a generating set of a symmetric group Sn. This paper reviews the existing permutation sorting and permutation decomposition procedures for sorting on graphs with line, star, complete, and ring topologies by adjacent swaps. We also provide concrete examples and our own implementation for this review paper in order to describe how abstract group-theoretical methods are used to find a minimum-length sequence of adjacent swaps needed to sort objects on those graphs.