> Amazingly, the graph diameter is often as high as 20: there are airports that can take 20 flights minimum to get between
I wonder if that's still true. It's hard to imagine. And just the thought of having to optimize that search function made my cortisol levels spike a bit.
> typically this will be a small airport in Alaska or Canada to another small airport in Africa or Indonesia
It's still mind blowing to me. Surely any Alaskan airport would be within 5 hops of Anchorage (or not have scheduled flights at all, fine, but that can't be the case here), likewise surely any Indonesian airport is within 5 hops of Jakarta, and Anchorage-Jakarta can certainly be done in 3 hops in a multitude of ways. But one of those assumptions is wrong by 7 hops!
There aren't even that many airports to consider, the same presentation gives 4000 as the number included in the analysis.
Maybe the graph topology is something like a series of tiny airports that each only connect to the next airport in the series, probably by the same flight that makes multiple stops (not unknown in island hopping, and maybe then in Alaska/Canada too). So you don't really board 20 planes but you do require 20 takeoffs and landings.
But it's definitely plausible the author half remembered the routes with 20 hops from some optimized search like this, and wrote the wrong thing in the presentation.
I would imagine we're seeing two to four groupings of sequential routes which are subsidized access. A floatplane which hits every island in the archipelago, like a bus route, before reaching the international airport with jets. Likewise with bush planes in Arctic villages, and regional turboprops that hit a sequence of rural airports because they only attract a few passengers a day on their entire route.