The other thing that was unstated in the article (from which the map came from) is that there seems to be a choice of overflights to get to ICN from North America:
a. Russia and North Korea (land). Probably not allowed at any price by North Korea.
b. Russia and North Korea (sea territory). Used by the "Kamchatka Route".
c. Russia and China (land). China probably charges too much or does not let overflights at any price (note that even Hong Kong SAR based Cathay Pacific avoids overflying China land other than the Hong Kong SAR when flying from HKG to non-China destinations). Otherwise, it may be an attractive way to fly from the "Kamchatka Route" but go over China to end up west of the Korean peninsula where ICN is.
d. Japan. Used by the "North Pacific Route" which is 30-60 minutes slower than the "Kamchatka Route", according to the map.
e. Russia and Japan (sea territory). Would be a longer version of the "Kamchatka Route".
f. No overflights. Not sure if it is possible to avoid overflying any other country by flying south of Japan (since Japan controls some islands in the area and other islands in the area are disputed), but it would likely add quite a bit of flying time even if it were possible.