极大外平面图的不可定向强最大亏格

Nonorientable Strong Maximum Genus of Maximal Outplanar Graph

强嵌入猜想称:任意2-连通图都可以强嵌入到某一曲面上．本文通过分析极大外平面图的结构以及强嵌入的特征,讨论了该图类的不可定向强最大亏格,并给出了一个复杂度为O(nlogn)的算法．其中部分图类的强最大亏格嵌入提供该图的一个少双圈覆盖．

Strong Embedding Conjecture states that： any 2-connected graph can be strongly embedded on some surface. In this paper, we discuss the structure of maximal planar graph and the characteristic of strong embedding, then give an O （n log n） complexity algorithm for computing the nonorientable strong maximum genus of maximal outplanar graph. From the strong embeddings of some graphs, a small circuit double cover can be obtained.