  Consider a random graph process with $n$ vertices corresponding to points
$v_{i} \sim {Unif}[0,1]$ embedded randomly in the interval, and where edges are
inserted between $v_{i}, v_{j}$ independently with probability given by the
graphon $w(v_{i},v_{j}) \in [0,1]$. Following Chuangpishit et al. (2015), we
call a graphon $w$ diagonally increasing if, for each $x$, $w(x,y)$ decreases
as $y$ moves away from $x$. We call a permutation $\sigma \in S_{n}$ an
ordering of these vertices if $v_{\sigma(i)} < v_{\sigma(j)}$ for all $i < j$,
and ask: how can we accurately estimate $\sigma$ from an observed graph? We
present a randomized algorithm with output $\hat{\sigma}$ that, for a large
class of graphons, achieves error $\max_{1 \leq i \leq n} | \sigma(i) -
\hat{\sigma}(i)| = O^{*}(\sqrt{n})$ with high probability; we also show that
this is the best-possible convergence rate for a large class of algorithms and
proof strategies. Under an additional assumption that is satisfied by some
popular graphon models, we break this "barrier" at $\sqrt{n}$ and obtain the
vastly better rate $O^{*}(n^{\epsilon})$ for any $\epsilon > 0$. These improved
seriation bounds can be combined with previous work to give more efficient and
accurate algorithms for related tasks, including: estimating diagonally
increasing graphons, and testing whether a graphon is diagonally increasing.
