图的曲面嵌入

Surface embedding of graphs

提供了曲面的一种多边形表示,它虽然由多面形表示演化而来,但使得图的曲面嵌入的存在性、计数、确定最大亏格等问题变得十分简单.多面形表示源于Heffter[1].Hilbert和Cohn Vossen提出过引线问题并将它与Heawood的地图着色猜想联系[2].经过近百年直至Ringal等获得证明[3,4].Edmonds(1960)[5]的多面形表示曾被广泛引用.但30余年后,才发现是Heffter的对偶形式.虽然多边形表示始于本文作者的专著[6,7],但至今才发现它在处理上述问题的效力.这就导致此文并为过渡到组合地图理论搭起一座桥梁.

This paper provided polygonal representation of surfaces.Although it was evaluated from polyhedral representation, many problems, e.g.,the existance and enumeration of graphs on surfaces, the determination of the maximjum genus of a graph could be solved much simpler in this way. Polyhedral representation was initiated by Heffter.Hilbert and CohnVossen posed the thread problem and had it related to the Heawood map color conjecture.The conjecture was not proved until Ringel et al.Edmonds(1960) polyhedral representation used to be cited very often for about three decades until it was found that Edmonds′ was the dual of Heffter′s.Polygonal representation began to appear first in the author′s monographs.However, its powerfullness had not been uncovered until this paper come out which was seen as a bridge to the combinatorial map theory.