Application Of Graph Theory In Channel Routing And Research Of Wiener Index

Channel routing problem is a critical issue in VLSI circuits.The network structure of the double-layer channel routing can be described by the vertical constraint and the horizontal constraint[1?2].In view of this special structure,the idea of graph theory can be applied to the double-layer channel routing.We study the vertical constraint graph with circles based on predecessors.A new algorithm of channel routing is utilized by finding and eliminating the critical network to solve the channel routing problem with one circle,which can get a lower bound of the track.In terms of more circles,we mainly study the routing algorithm from the two kinds of constraint graphs of the nodes.A routing algorithm about containing one pair and two pairs of null nodes is provided by researching a kind of channel routing problem in the vertical constrained graphs,which can get a better track height,and the detailed routing process is given.Wiener index is also an important application of graph theory,which is widely used in theoretical chemistry.The Wiener index refers to the sum of the distances of all points in a graph,expressed as follows:(?)Wiener index[3].is mainly embodied in the molecular structure of the characteristics,belonging to the topological index.There are a wide range of applications in many areas,such as physics,chemistry,biology,communications and so on.In this paper,we discuss the upper and lower bounds of the sum of the squares of all pairs of vertexes,respectively,in the case of a vertex and chromatic number or vertex number and number of clusters,(?)The index is based on the Wiener index and has some research significance for the molecular structure.