四正则图的自动生成及纵横嵌入的线性算法

A Linear Algorithm for Automatic Generation and Rectilinear Embeddings of Four Regular Graph

刘彦佩教授论述的纵横嵌入术已为超大规模集成电路 (VLSI)的平面设计提供了较完备的理论体系 ,本文以此为依据建立的算法能自动生成任意点数的四正则图例 ,并对其进行双极定向和双极标数 ,进而画出其纵横嵌入图 .在对四正则图进行双极定向时 ,根据吸收规则的原理 ,设计了一种在计算机上易于实现的算法 ,该算法已成功地绘制了含有几个点及至近千个点的四正则图的纵横嵌入图 .

Rectilinear embedding that Professor Yanpei Liu described in books has provided a theoretic system for the planar design of VLSI circuit. According to this system, the paper shows the algorithm that can generate the graph example of the four regular graph with any number of vertices and determines its bipolar orientation and bipolar numbering, and draws its rectilinear embedding graph. For determining the bipolar orientation of four regular graph, the authors design an algorithm that can be more easily implemented by computer on the base of the absorbing rule. We have successfully drawn the rectilinear embeddings of many four regular graphs with a few and even nearly one thousand vertices.