Permutation Graphs: Hamiltonian Paths

Abstract

Permutation graphs, a well-known class of perfect graphs, has attracted the attention of numerous researchers. There are two noteworthy representations of permutation graphs. Permutation diagrams have been widely employed in theoretical and application research. The $2$-dimensional Euclidean representation suggested by Ore is relatively unknown and unexplored. In this paper, we demonstrate the utility of the latter representation in the investigation of the Hamiltonian Path problem in permutation graphs.