Approximating layout problems on random graphs Original Research Article

We show that, with overwhelming probability, several well-known layout problems are approximable within a constant for random graphs drawn from the G(n,pn) model where C/n⩽pn⩽1 for all n big enough and for some properly characterized parameter C>1. In fact, our results establish that, with overwhelming probability, the cost of any arbitrary layout of such a random graph is within a constant of the optimal cost.