OJDM  Vol.10 No.1 , January 2020
Improved Approximation of Layout Problems on Random Graphs
Abstract: Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 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ö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.
Cite this paper: Cheung, K. and Girardet, P. (2020) Improved Approximation of Layout Problems on Random Graphs. Open Journal of Discrete Mathematics, 10, 13-30. doi: 10.4236/ojdm.2020.101003.

[1]   Díaz, J., Petit, J. and Serna, M. (2002) A Survey of Graph Layout Problems. ACM Computing Surveys, 34, 313-356.

[2]   Lengauer, T. (1981) Black-White Pebbles and Graph Separation. Acta Informatica, 16, 465-475.

[3]   Gavril, F. (2011) Some NP-Complete Problems on Graphs. 2011 45th Annual Conference on Information Sciences and Systems, Baltimore, MD, 23-25 March 2011.

[4]   Cheung, K., Girardet, P., Moatamed, A. and Ruiz, E. (2018) On a Directed Layout Problem. Manuscript in Preparation.

[5]   Brandes, U. and Fleischer, D. (2009) Vertex Bisection Is Hard, too. Journal of Graph Algorithms and Applications, 13, 119-131.

[6]   Garey, M.R. and Johnson, D.S. (1979) Computers and Intractibility: A Guide to the Theory of NP Completeness. Freeman and Co., New York.

[7]   Díaz, J., Petit, J., Trevisan, L. and Serna, M. (2001) Approximating Layout Problems on Random Graphs. Discrete Mathematics, 235, 245-253.

[8]   Gilbert, E.N. (1959) Random Graphs. The Annals of Mathematical Statistics, 30, 1141-1144.

[9]   Barak, A.B. and Erdös, P. (1984) On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph. SIAM Journal on Algebraic Discrete Methods, 5, 508-514.

[10]   Hoeffding, W. (1963) Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58, 13-30.