> 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.
It may also depend on optimizations. Potentially you may be able to do fewer hops but if the schedules have 1/week flights they may end up taking 2 weeks calendar time for 7 hops while 20 hops gets you there in 4 days. If the window used for the graph creation doesn't cover enough schedule time, more optimal routes may fall off the edges.
This doesn't match the phrasing in the presentation, I would expect "the graph has diameter 20" to be defined without any reference to the weights of the edges (whether in flying time, total time, cost...)
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.
Thinking about it, I bet you can prove this is the topology. If the graph is generally densely connected (almost all nodes have 3+ destinations) then the diameter can't be that high compared to the size of the graph. Proof left to the reader. So either there are chains like described above at the edges, or there's a chain like that separating two parts of the graph (suppose there was only one route connecting the US to Europe, and it stopped in Newfoundland, Keflavik and Shannon). The last possibility is obviously nonsense, though, we know that major airports are densely connected.
Yeah, so far CKX is the airport I can find with the most hops to Anchorage (4, but 3 to Fairbanks which is also fairly well connected). YGZ is likewise 4 hops to Ottawa, and I can't find anything higher in Canada (there are a few that are 4 hops to Montreal in northern Quebec). Nor can I find anything in Greenland more than 4 hops from Copenhagen, Keflavik, or Gatwick (hilariously, that's the fewest-hop big airport for some routes due to flying through Akureyri, which is connected to RKV rather than KEF). There must be some island hopping chain somewhere in the Pacific (or perhaps in the Indian Ocean?) but it's not so easy to find. It seems you're usually a few hops from either Tahiti, Hawaii or Fiji...
I have heard about some routes in northern Norway that have a lot of short stops to pickup/unload passengers (like a flying bus). I don't know if they still exist
Has to be worse than that. 20 is still way too many degrees of separation if every region operated on a hub and spoke model.
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.
> 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.