For a given ordered graph (G, <), we consider the smallest (strongly) chordal graph G′ containing G with < as a (strongly) perfect elimination ordering. We call (G, <) a compact representation of G′. We show that the computation of a depth-first search tree and a breadth-first search tree can be done in polylogarithmic time with a linear processor number with respect to the size of the compact representation in parallel. We consider also the problems to find a maximum clique and to develop a data structure extension that allows an adjacency query in polylogarithmic time.