图的双极定向的一种新算法

An Algorithm for Bipolar Orientations of Graph

基于刘彦佩教授的吸收规则,构造了一个计算双极定向的线性算法.并证明了该算法是简单易行的.

Bipolar orientation have a wide range of applications in VLSI design and also is the basis for many graph drawing algorithms. In this paper we give a linear algorithm to compute bipolar orientation, this algorithm is based on the absorption rule presented by Professor Liu Yanpei. We analyzed the fundamental circuit of the undirected graph, and find out two basic configurations of the circuit. By the optimization of these two configurations, the algorithm of the bipolar orientation is given.