Triangular Mesh Reordering - Huddling Triangles
There appears to be a solution used by game programmers that both optimizes graphics hardware cache utilization and facilitates mesh connectivity compression. It is Tom Forsyth's Linear-Speed Vertex Cache Optimisation described here: https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html 

The algorithm uses a heuristic based on modeling the GPU vertex cache to produce a sequence of triangles with high locality and vertex reuse. The pattern produced is reportedly not unlike the Hilbert curve. The algorithm has linear time complexity.

The master thesis "Efficient Triangle Reordering for Improved Vertex Cache Utilisation in Realtime Rendering" (http://www.martin.st/thesis/) contains a C++ implementation and also seems to describe an improved algorithm.