Planar graph

Monge property

平面グラフとは、エッジを交叉させずに平面に描けるグラフのこと 平面グラフの距離行列はMonge propertyという性質を満足する 平面グラフの頂点u,vから、別の頂点x,yへの最短距離を考えるとき d(u,x)+d(v,y)とd(u,y)+d(v,x)とのどちらが小さいかを問題にした…