  We propose a class of methods for graphon estimation based on exploiting
connections with nonparametric regression. The idea is to construct an ordering
of the nodes in the network, similar in spirit to Chan and Airoldi (2014).
However, rather than only considering orderings based on the empirical degree
as in Chan and Airoldi (2014), we use the nearest neighbor algorithm which is
an approximating solution to the traveling salesman problem. This in turn can
handle general distances $\hat{d}$ between the nodes, something that allows us
to incorporate rich information of the network. Once an ordering is
constructed, we formulate a 2D grid graph denoising problem that we solve
through fused lasso regularization. For particular choices of the metric
$\hat{d}$, we show that the corresponding two-step estimator can attain
competitive rates when the true model is the stochastic block model, and when
the underlying graphon is piecewise H\"{o}lder or it has bounded variation.
