Research ArticleOpen AccessGoogle Scholar indexed
Improved Approximation of Layout Problems on Random Graphs
School of Mathematics and Statistics, Carleton University, Ottawa, ON, Canada
Department of Mathematics, University of California San Diego, La Jolla, CA, USA
- 1 School of Mathematics and Statistics, Carleton University, Ottawa, ON, Canada
- 2 Department of Mathematics, University of California San Diego, La Jolla, CA, USA
Open Journal of Discrete Mathematics·Volume 10 (2019)·Pages 13–30·Published 11 November 2019·DOI10.4236/ojdm.2020.101003
Copy link · social · email
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.
KeywordsGraph ArrangementsRandom GraphsApproximation AlgorithmsUndirected GraphsDirected Acyclic Graphs
- Díaz, J., Petit, J. and Serna, M. (2002) A Survey of Graph Layout Problems. ACM Computing Surveys, 34, 313-356. https://doi.org/10.1145/568522.568523
- Lengauer, T. (1981) Black-White Pebbles and Graph Separation. Acta Informatica, 16, 465-475. https://doi.org/10.1007/BF00264496
- Gavril, F. (2011) Some NP-Complete Problems on Graphs. 2011 45th Annual Conference on Information Sciences and Systems, Baltimore, MD, 23-25 March 2011.
- Cheung, K., Girardet, P., Moatamed, A. and Ruiz, E. (2018) On a Directed Layout Problem. Manuscript in Preparation.
- Brandes, U. and Fleischer, D. (2009) Vertex Bisection Is Hard, too. Journal of Graph Algorithms and Applications, 13, 119-131. https://doi.org/10.7155/jgaa.00179
- Garey, M.R. and Johnson, D.S. (1979) Computers and Intractibility: A Guide to the Theory of NP Completeness. Freeman and Co., New York.
- Díaz, J., Petit, J., Trevisan, L. and Serna, M. (2001) Approximating Layout Problems on Random Graphs. Discrete Mathematics, 235, 245-253. https://doi.org/10.1016/S0012-365X(00)00278-8
- Gilbert, E.N. (1959) Random Graphs. The Annals of Mathematical Statistics, 30, 1141-1144.
- 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.
- Hoeffding, W. (1963) Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58, 13-30. https://doi.org/10.1080/01621459.1963.10500830