Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$? This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results.

Specifically, I'm interested in seeing some hardness proofs for problems that are believed to have roughly $\Omega(n^3)$ lower bounds, and I say roughly to allow for slightly subcubic improvements by playing with the word size (such as that for 3SUM by Barab et al. [via Springer]). I would be happy to keep problems in the decision tree model if it simplifies the responses.

From Robin's post, I learned about Jeff Erikson's paper which gives a $\Omega(n^3)$ lower bound for 5SUM (more accurately, he shows that $k$-SUM runs in $\Omega (n^{\lceil k/2 \rceil})$ time in general). 

Do papers or other references exist using such reductions to conjecture cubic lower bounds for problems in computational geometry or graph theory?
I think the paper "Subcubic Equivalences Between Path, Matrix, and Triangle
Problems" by V. Vassilevska Williams and R. Williams is what you're looking for. Its abstract contains the list of the following problems on graphs:


The all-pairs shortest paths problem on weighted digraphs (APSP).
Detecting if a weighted graph has a triangle of negative total edge weight.
Listing up to $n^{2.99}$ negative triangles in an edge-weighted graph.
The replacement paths problem on weighted digraphs.
Finding the second shortest simple path between two nodes in a weighted digraph.


According to the abstract the paper is about the following:


  We define a notion of subcubic reducibility, and show that many important problems on graphs and matrices solvable
  in $O(n^3)$ time are equivalent under subcubic reductions.