%0 Journal Article
%T Improved Approximation of Layout Problems on Random Graphs
%A Kevin K. H. Cheung
%A Patrick Girardet
%J Open Journal of Discrete Mathematics
%P 13-30
%@ 2161-7643
%D 2020
%I Scientific Research Publishing
%R 10.4236/ojdm.2020.101003
%X Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, <em>Discrete Mathematics</em>, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erd<span style=\"white-space:nowrap;\">&amp;#246;</span>s-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.
%K Graph Arrangements
%K Random Graphs
%K Approximation Algorithms
%K Undirected Graphs
%K Directed Acyclic Graphs
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=97768