Start with a triangle embedded in the plane. In each step, choose a bounded face uniformly at random, add a vertex inside that face and join it to the vertices of the face. After $n-3$ steps, we obtain a random triangulated plane graph with $n$ vertices, which is called a random Apollonian network. Asymptotically almost surely, the diameter of the resulting network is is asymptotic to $c \log n$, where c ≈ 1.668, and the longest path length is at most $n^\delta$ for some $\delta<1$.

The latter result refutes a conjecture of Frieze and Tsourakakis, and confirms a conjecture of Cooper and Frieze. For its proof, we bound the size of the largest regular ($r$-ary) subtrees of the random recursive tree with $t$ vertices.

Includes joint work with Andrea Collevecchio, Ehsan Ebrahimzadeh, Linda Farczadi, Pu Gao, Abbas Mehrabian, Cristiane M. Sato, Jonathan Zung.