Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?
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.