Ever heard of an elevated highway, ramp, flying junction, bridge, or tunnel?

I mean, yeah the topology is not as complex as a pure unrestricted 3d space but it's also more complex than pure 2d space. It's a search through a space, and it's complex, I don't know if nitpicking about the topology adds a lot here?

That's still 2D space. A car simply can't move along the z axis, so the fact that the road itself moves in 3 dimensions is irrelevant.

Even navigational paths that consider all of the junctions, ramps, etc. are simply reduced to a weighted graph with no notion of any dimensions beyond forward and backwards.