A digraph is a graph in which each edge has an orientation. A linear directed path, , is a path whose all edges have the same orientation. A linear simple graph
Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we sho