Some Problems Of Graph Layout

Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. A large number of relevant problems in different domains can be formulated as graph layout problems. These include optimization of networks for parallel computer architectures, VLSI circuit design, information retrieval, numerical analysis, computational biology, graph theory and scheduling.Give a graph G＝(V, E), a layout of the graph is a bijection from its vertices set V(G) to the set [|V(G)|]={1.2,...,|V(G)|}, We denote by Φ(G) the set of all layout of the graph G. A layout costs of G is a real-valued function onΦ(G). The graph layout problem is find a layout of an graph in such way that the layout cost is optimized.Give a layout of a graph G,φ is a layout of G, let uv be a edge of G, the length of uv is｜φ(u)-φ(v)|. The sum of the length of all the edges is a layout cost of G, denote by LA(φ, G), we call it minimum linear arrangement.This paper contains three parts:(1) Basic concepts and definitions of graph layout, some property of Minimum Linear Arrangement.(2) Minimum Linear Arrangement of Pm△G:consider the relationship between the layout of Pm△G and G.(3) Minimum Linear Arrangement of Pm⊙Pn:give upper and lower bounds of the Minimum linear arrangement of Pm⊙Pn.