Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Bounded-degree graphs can have arbitrarily large slope numbers. | Bounded-degree graphs can have arbitrarily large slope numbers János Pach and Domotor Pắlvôlgyi Rényi Institute Hungarian Academy of Sciences Submitted Oct 21 2005 Accepted Dec 22 2005 Published Jan 7 2006 Mathematics Subject Classification 05C62 Abstract We construct graphs with n vertices of maximum degree 5 whose every straight-line drawing in the plane uses edges of at least n1 6-o 1 distinct slopes. A straight-line drawing of a graph G V G E G is a layout of G in the plane such that the vertices are represented by distinct points the edges are represented by possibly crossing line segments connecting the corresponding point pairs and not passing through any other point that represents a vertex. If it creates no confusion the vertex edge of G and the point segment representing it will be denoted by the same symbol. Wade and Chu WC94 defined the slope number sl G of G as the smallest number of distinct edge slopes used in a straight-line drawing of G. Dujmovic et al. DSW04 asked whether the slope number of a graph of maximum degree d can be arbitrarily large. The following short argument shows that the answer is yes for d 5. Define a frame graph F on the vertex set 1 . ng by connecting vertex 1 to 2 by an edge and connecting every i 2 to i 1 and i 2. Adding a perfect matching M between these n points we obtain a graph G M F u M. The number of different matchings is at least n 3 n 2. Let G denote the huge graph obtained by taking the union of disjoint copies of all Gm. Clearly the maximum degree of the vertices of G is five. Suppose that G can be drawn using at most S slopes and fix such a drawing. For every edge ij 2 M label the points in GM corresponding to i and j by the slope of ij in the drawing. Furthermore label each frame edge ij ji jj 2 by its slope. Notice that no two components of G receive the same labeling. Indeed up to translation and scaling the labeling of the edges uniquely determines the positions of the points representing the vertices of GM. .
