In this paper, we present efficient layouts for complete graphs and star graphs. We show that an N-node complete graph can be optimally laid out using N 2 /4 tracks for a colinear layout, and can be laid out in N 4 /16 + o(N 4 ) area for a 2D layout. We also show that an N-node star graph can be laid out in N 2 /16 + o(N 2 ) area, which is smaller than any possible layout of a similar-size hypercube. This solves an open question posed by Akers and Krishnamurthy in 1986. Both the layouts of complete graphs and star graphs are optimal within a factor 1 + o(1).