> Maintaining a dependency graph would give us the most efficient updates, but it’s often an overkill for a spreadsheet.

It's not overkill at all. In fact, it's absolutely necessary for all but the simplest toy examples.