有向平面グラフがあります。したがって、平面埋め込みを行うことができます。ノード s と t が必要で、特定の埋め込みに従って s と t の間の左端のパスを見つけたいと思います。
左は、コメントで説明されているデビッドと定義されています。つまり、「左」は無限面と時計回り/反時計回りの規則に関して定義されます。パス p は、サイクル p*rev(q) が他の面と同様に無限面の巻き上げに関して少なくとも反時計回りである場合、同じ端点を持つパス q の左側にあります。
そんなことがあるものか？パスが別のパスから離れているかどうかをプログラムに伝える方法がわかりません。私はいくつかの論文を読みましたが、それを実装する方法を説明していませんでした。誰かがアイデアを持っていますか？