It depends on the shape of your domain and presence of local refinement, but for isotropic domains in $d$ dimensions, the minimum achievable bandwidth scales as $N^{\frac{d-1}{d}}$ where $N$ is the total number of elements (or vertices). You can use a method like Reverse Cuthill-McKee to produce reasonable low-bandwidth orderings.
However, minimizing bandwidth is not the objective of ordering techniques for sparse direct solvers. Indeed, this will lead to $N^{\frac{2d-1}{d}}$ nonzeros in the factors, but optimal orderings (usually found by orderings such as nested dissection which is used by most packages) have $N \log N$ nonzeros in 2D and $N^{4/3}$ nonzeros in 3D. See George, Liu, and Ng's book for details on this result.
Visual comparison of orderings
The following graphically compares orderings for the 5-point Laplacian on a $12\times 12$ regular grid. For each ordering, I report the number of nonzeros in the $L$ and $U$ factors for a $100\times 100$ grid. Note that the difference is much more pronounced in 3D. You can plot the fill matrices and diagnostics with PETSc:
$ cd $PETSC_DIR/src/ksp/ksp/examples/tutorials && make ex2
$ ./ex2 -m 12 -n 12 -ksp_view -pc_type lu -pc_factor_mat_ordering_type nd -mat_view_draw -draw_pause 2
Matrix $A$ and factor $L$ in natural ordering (1990198 nonzeros)
Matrix $A$ and factor $L$ in Reverse Cuthill-McKee ordering (1353100 nonzeros)
Matrix $A$ and factor $L$ in Nested Dissection ordering (382934 nonzeros)
On the other hand, low-bandwidth orderings are often reasonable orderings (algorithmically) for incomplete factorization and relaxation like SOR and tend to reuse cache well (so are good for throughput). For maximum performance on structured grids, you can skip the column indices (because they have regular structure) and only store the stencil coefficients, or even recompute the coefficients on the fly. It is well worth careful profiling and analysis using a performance model to determine whether optimizations like this are worth the implementation time and reduced flexibility.
