Treewidth of Erdös-Rényi Random Graphs, Random Intersection Graphs, and Scale-Free Random Graphs

Abstract

We prove that the treewidth of an Erdös-Rényi random graph $\rg{n, m}$ is, with high probability, greater than $\beta n$ for some constant $\beta >0$ if the edge/vertex ratio $\frac{m}{n}$ is greater than 1.073. Our lower bound $\frac{m}{n}>1.073$ improves the only previously-known lower bound. We also study the treewidth of random graphs under two other random models for large-scale complex networks. In particular, our result on the treewidth of \rigs strengths a previous observation on the average-case behavior of the \textit{gate matrix layout} problem. For scale-free random graphs based on the Barabási-Albert preferential-attachment model, our result shows that if more than 12 vertices are attached to a new vertex, then the treewidth of the obtained network is linear in the size of the network with high probability.

References in corpus (1)

• The Degree Distribution of Random k-Trees