Estimates for the diameter of a (nice) surface? The Question
Let $M$ be a compact, connected, orientable surface without boundary of bounded genus smoothly embedded in $\mathbb{R}^3$; define the diameter $d_M$ of $M$ as the maximum minimal (geodesic) distance between any pair of points $x,y \in S$.  My question is:

What's a good estimate for $d_M$?

To make this question more interesting, let's try to avoid pathological examples.  Because this is MathOverflow I'm a little insecure about the best way to say this, but let me try the following: suppose that the surface has fixed area and bounded curvature.  For instance, one might require that the Willmore energy $\int_M H^2 dA$ is bounded, where $H$ is the mean curvature.  This way we avoid examples like an incredibly long, thin (capped) cylinder which has nearly zero surface area but enormous diameter, or similarly an infinitely thin infinitely long spiral.  These types of examples tend to confound estimates that otherwise work pretty well.
To understand the scope of the question it may help to know that I really want to be able to evaluate this estimate (using a 5-year-old laptop, say) for a simplicial approximation of $S$.  For this reason, I prefer to work with quantities that can be computed efficiently like surface area, enclosed volume, mean/Gaussian curvature, etc.  I'm willing to compute a few eigenvalues of the Laplacian (e.g., the smallest and largest), but I refuse to compute all of them.  I'm not terribly excited about estimates that bound $d_M$ from only one side.
One Approach
Here's one idea I had based on some rough intuition about Laplacian eigenfunctions.  It works surprisingly well in practice (e.g., within 20% of the actual diameter for a wide variety of example surfaces), but I have trouble saying anything concrete about it.
Let $\phi$ be an eigenfunction of the scalar Laplace-Beltrami operator $\Delta$ on $M$, i.e., $\phi$ has unit $L^2$ norm and satisfies $\Delta \phi = \lambda \phi$ for some eigenvalue $\lambda \in \mathbb{R}$.  (I'll adopt the convention that $\Delta$ is positive-semidefinite so that $\lambda \geq 0$.)  Then we have
$$ \int_M |\nabla\phi|^2 dA = \int_M \Delta \phi \cdot \phi = \int_M \lambda \phi^2 dA = \lambda \int_M \phi^2 = \lambda,$$
hence $\|\nabla \phi\|_{L^2} = \sqrt{\lambda}$.
Now consider the "first" nontrivial eigenfunction $\phi$, i.e., the one corresponding to the smallest nonzero eigenvalue $\lambda$.  I'm going to make a fairly crude approximation and replace $|\nabla \phi|$ at every point with the value
$$ g := \frac{\phi_\max-\phi_\min}{d_M}, $$
where $\phi_\max$ and $\phi_\min$ are the maximum and minimum (pointwise) values of $\phi$.
Where does this idea come from?  The idea is best illustrated in 1D -- consider the circle $S^1$, which we can identify with the interval $[0,2\pi) \subset \mathbb{R}$.  In this case the first eigenfunction $\phi$ looks like $\sqrt{\pi}\cos(x)$ -- just one full oscillation as we go from zero to $2\pi$:
 (source)
In this case the value $g$ is an overestimate of $|\nabla \phi|$ in some places and an underestimate in others.  So, we substitute $g$ for $|\nabla \phi|$ in the first relationship above and get
$$ A g^2 \approx \lambda, $$
where $A$ is the total surface area.  Solving for $d_M$ gives us an approximation
$$ d_M \approx (\phi_\max - \phi_\min)\sqrt{A/\lambda}. $$
You'll notice my liberal use of "$\approx$" here, because I haven't been able to establish any hard bounds!  But again, keep in mind that however crude the argument may be, this approximation appears to work unreasonably well for "reasonable" surfaces.
Still, it would be nice to be able to say something concrete about this approximation (maybe with additional restrictions on $M$) or to have an alternative approximation with established bounds.
Thanks!
 A: This paper of Peter Topping doesn't really meet all of your criteria, but may be of interest to you. For surfaces it bounds the diameter from above in terms of the $L^1$ norm of the mean curvature of the surface.
A: I am not sure that computing surface area, volume, curvature, or eigenvalues of the Laplacian, represents
the best route.
To expand on Thomas Richard's points: The diameter of the 1-skeleton can be found in roughly $n^2$ time, where $n$ is the number of vertices.
It is a relatively straightforward algorithm, employing Disjkstra's shortest path algorithm.
You can find existing implementations, e.g., this igraph one.
It's even a function in Mathematica/Combinatorica: Diameter[g].
It of course would only yield an approximate geometric diameter, depending on the coarseness of your mesh.  But you are only seeking estimates anyway.
It could definitely run on a 5-year old laptop, because the space requirements of
Dijkstra's algorithm are only $O(n)$, which you need already to store your mesh. 
Whether you can wait out $O(n^2 \log n)$ computation
time depends on your laptop's processor (and your patience!).
Edit. See comments for approximation algorithms.
I don't know of computational geometry work that computes the true geometric diameter for arbitrary genus. I have written papers on the genus-zero case
myself, and already it is intricate: about $n^8$. 
("Star Unfolding of a Polytope with Applications," SIAM J. Comput. 26, pp. 1689-1713).
So the best route seems to be computing the diameter of the 1-skeleton of an approximate triangulation. To increase precision, remesh at a finer scale.  There are many algorithms
available for this, e.g., "Geodesic-based surface remeshing," Sifri, Sheffer, Gotsman.
A: This seems highly related to:
http://en.wikipedia.org/wiki/Cheeger_constant
