基于四剖分的纵横嵌入问题研究

Research on the Quadrangulations in Rectilinear Embedding

基于纵横嵌入问题的函数方程理论,建立了两类带多参数的四剖分图(四正则图)的生成函数方程,并应用拉格朗日反演得到了相应纵横嵌入图的简单计算公式.进而通过建立外平面图与哈密尔顿图的关系,推出了哈密尔顿的四剖分图的计数结果.四剖分图在超大规模集成电路设计,图论的高斯交叉数和拓扑学的扭结问题及其它纵横嵌入图的计数上都有着广泛的应用.

Based on the theory of functional equations in rectilinear embedding,we provide generating functions for two types of quadrangulations（quartic maps）with mapmultiple parameters and derive explicit formulae by employing Lagrangian inversion. Furthermore,we establish a relation between outer planar graph and Hamilton graph,and obtained the counting result of Hamilton quadrangulation. Quadrangulationsare widely used in VLSI,in the Gaussian crossing of graph theory,in the knot problem of topology,and in the enumeration of other kinds of maps in rectilinear embeddings.