The number of slopes of the graph

Figure of the graph of Peterson with the number of slopes 3

In graph visualization and number of slopes of a graph is the minimum possible number of different slope coefficients of the edges in the graph drawing, in which the vertices are represented by the points of the Euclidean plane , and the edges are segments that do not pass through vertices that are not incident to these edges.

Content

Full Counts

Although close problems of combinatorial geometry were studied earlier (by Scott in 1970 and Jamison in 1984), the problem of determining the number of slopes of the graph was posed by Wade and Chu ^[1] , showing that the number of slopes of the graph with n vertices of the complete graph K _n is exactly n . A graph drawing with such a number of slopes can be obtained by arranging the vertices of the graph in the corners of a regular polygon .

Relationship with the degree of a graph

It is clear that the number of slopes of a graph with maximum degree d is not less $\lceil d/2\rceil$ ${\ displaystyle \ lceil d / 2 \ rceil}$ , since a maximum of two incident edges of a vertex of degree d can lie on one straight line (have one slope). More precisely, the number of slopes is not less than the linear tree of the graph , since the edges of one slope should form a linear forest, and the linear tree, in turn, is not less $\lceil d/2\rceil$ ${\ displaystyle \ lceil d / 2 \ rceil}$ .

There are graphs with a maximum degree of five that have an arbitrarily large number of slopes ^[2] . However, any graph with a maximum degree of three has at most four slopes ^[3] . The result of Wade and Chu ( Wade, Chu (1994 )) for the complete graph K ₄ shows that this boundary is exact. Not every set of four slopes is suitable for drawing all graphs of degree 3 - a set of slopes is suitable for drawing if and only if they are the slopes of the sides and diagonals of a parallelogram . In particular, any graph of degree 3 can be drawn so that its edges are either parallel to the axes or parallel to the main diagonals of the integer lattice ^[4] . It is unknown whether or not the number of slopes of graphs with a maximum degree of four is limited ^[5] .

The Keseg, Paha, and Palveldi method ^[6] combining the packing of circles and a quadrant tree to obtain a limited number of slopes for planar graphs with a limited degree

Planar graphs

As shown by Keseg, Pach, and Palveldi ( Keszegh, Pach, Pálvölgyi (2011 )), any planar graph has a flat drawing in the form of straight segments , in which the number of different slopes is a function of the degree of the graph. Their proof follows the construction of Malitz and Papakostas ( Malitz, Papakostas (1994 )) to limit the planar graphs as a function of degree. The degree is limited by supplementing the graph to the maximum planar graph without increasing its degree by more than a constant factor, and then the circle packing theorem is applied to represent this extended graph as a set of circles tangent to each other. If the degree of the initial graph is limited, the ratio of the radii of adjacent circles in the package will also be limited ^[7] , which, in turn, implies that the use of a quadrant tree for all vertices of the graph at a point inside the circle gives slopes, which are relations of small integers. The number of different slopes obtained in this construction is an exponent of the degree of the graph.

Difficulty

The problem of determining whether the number of slopes is equal to two is an NP-complete problem ^[8] ^[9] ^[10] . It follows that it is an NP-difficult task to determine the number of slopes of an arbitrary graph or to approximate this number with guaranteed efficiency better than 3/2.

Whether a planar graph is a planar drawing with two slopes is also an NP-complete problem ^[11] .

Notes

↑ Wade, Chu, 1994 .
↑ Independently proved by Barat, Matoushek, Wood ( Barát, Matoušek, Wood (2006 )) and Pakh, Palveldi ( Pach, Pálvölgyi (2006 )), when they solved the problem posed by Dujmovic, Suderman and Sharir ( Dujmović, Suderman, Wood (2005 )). See Theorems 5.1 and 5.2 by Pach and Sharir ( Pach, Sharir (2009 )).
↑ Mukkamala, Szegedy (2009 ), who improved the earlier result of Keseg, Palveldi, Tota ( Keszegh, Pach, Pálvölgyi, Tóth (2008 ). See Theorem 5.3 by Pach and Sharir ( Pach, Sharir (2009 )).
↑ Mukkamala, Pálvölgyi, 2012 .
↑ Pach, Sharir, 2009 .
↑ Keszegh, Pach, Pálvölgyi, 2011 .
↑ Hansen, 1988 .
↑ Formann, Hagerup, Haralambides, Kaufmann, 1993 .
↑ Eades, Hong, Poon, 2010 .
↑ Maňuch, Patterson, Poon, Thachuk, 2011 .
↑ Garg, Tamassia, 2001 .

Literature

János Barát, Jiří Matoušek, David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness // Electronic Journal of Combinatorics . - 2006. - T. 13 , no. 1 . - S. R3 .
Vida Dujmović, Matthew Suderman, David R. Wood. Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers / János Pach. - Berlin: Springer-Verlag, 2005. - T. 3383. - S. 122-132. - ( Lecture Notes in Computer Science ). - DOI : 10.1007 / 978-3-540-31843-9_14 .
Peter Eades, Seok-Hee Hong, Sheung-Hung Poon. Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers / David Eppstein, Emden R. Gansner. - Berlin: Springer, 2010 .-- T. 5849. - S. 232–243. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 978-3-642-11805-0_23 .
M. Formann, T. Hagerup, J. Haralambides, M. Kaufmann, FT Leighton, A. Symvonis, E. Welzl, GJ Woeginger. Drawing graphs in the plane with high resolution // SIAM Journal on Computing . - 1993. - T. 22 , no. 5 . - S. 1035-1052 . - DOI : 10.1137 / 0222063 .
Ashim Garg, Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing // SIAM Journal on Computing . - 2001. - T. 31 , no. 2 . - S. 601-625 . - DOI : 10.1137 / S0097539794277123 .
Lowell J. Hansen. On the Rodin and Sullivan ring lemma // Complex Variables, Theory and Application. - 1988. - T. 10 , no. 1 . - S. 23-30 . - DOI : 10.1080 / 17476938808814284 .
Robert E. Jamison. Planar configurations which determine few slopes // Geometriae Dedicata . - 1984 .-- T. 16 , no. 1 . - S. 17–34 . - DOI : 10.1007 / BF00147419 .
Balázs Keszegh, János Pach, Dömötör Pálvölgyi. Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. - Heidelberg: Springer, 2011 .-- T. 6502. - S. 293-304. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 978-3-642-18469-7_27 .
Balázs Keszegh, János Pach, Dömötör Pálvölgyi, Géza Tóth. Drawing cubic graphs with at most five slopes // Computational Geometry: Theory and Applications . - 2008. - T. 40 , no. 2 . - S. 138–147 . - DOI : 10.1016 / j.comgeo.2007.05.05.003 .
Seth Malitz, Achilleas Papakostas. On the angular resolution of planar graphs // SIAM Journal on Discrete Mathematics . - 1994. - T. 7 , no. 2 . - S. 172–183 . - DOI : 10.1137 / S0895480193242931 .
Ján Maňuch, Murray Patterson, Sheung-Hung Poon, Chris Thachuk. Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers / Ulrik Brandes, Sabine Cornelsen. - Heidelberg: Springer, 2011 .-- T. 6502. - S. 305-316. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 978-3-642-18469-7_28 .
Padmini Mukkamala, Mario Szegedy. Geometric representation of cubic graphs with four directions // Computational Geometry: Theory and Applications . - 2009. - T. 42 , no. 9 . - S. 842–851 . - DOI : 10.1016 / j.comgeo.2009.01.005 .
Padmini Mukkamala, Dömötör Pálvölgyi. Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers / Marc van Kreveld, Bettina Speckmann. - Springer, 2012. - T. 7034. - S. 254–265. - (Lecture Notes in Computer Science). - DOI : 10.1007 / 978-3-642-25878-7_25 .
János Pach, Dömötör Pálvölgyi. Bounded-degree graphs can have arbitrarily large slope numbers // Electronic Journal of Combinatorics . - 2006. - T. 13 , no. 1 . - S. N1 .
János Pach, Micha Sharir. Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. - American Mathematical Society , 2009. - T. 152. - S. 126–127. - (Mathematical Surveys and Monographs).
PR Scott. On the sets of directions determined by n points // American Mathematical Monthly . - 1970 .-- T. 77 . - S. 502–505 . - DOI : 10.2307 / 2317384 .
GA Wade, J.-H. Chu. Drawability of complete graphs using a minimal slope set // The Computer Journal . - 1994 .-- T. 37 , no. 2 . - S. 139–142 . - DOI : 10.1093 / comjnl / 37.2.139 .

[_78013e69d263eac9-1] Wade, Chu, 1994 .

[2] Independently proved by Barat, Matoushek, Wood ( Barát, Matoušek, Wood (2006 )) and Pakh, Palveldi ( Pach, Pálvölgyi (2006 )), when they solved the problem posed by Dujmovic, Suderman and Sharir ( Dujmović, Suderman, Wood (2005 )). See Theorems 5.1 and 5.2 by Pach and Sharir ( Pach, Sharir (2009 )).

[3] Mukkamala, Szegedy (2009 ), who improved the earlier result of Keseg, Palveldi, Tota ( Keszegh, Pach, Pálvölgyi, Tóth (2008 ). See Theorem 5.3 by Pach and Sharir ( Pach, Sharir (2009 )).

[_84517febaaefb9dc-4] Mukkamala, Pálvölgyi, 2012 .

[_a57769b9573aef95-5] Pach, Sharir, 2009 .

[_0d9c4d04d8ff3024-6] Keszegh, Pach, Pálvölgyi, 2011 .

[_84304ea7e554d0f4-7] Hansen, 1988 .

[_fae9891a5f33cb24-8] Formann, Hagerup, Haralambides, Kaufmann, 1993 .

[_f3c67ec7c94cba3a-9] Eades, Hong, Poon, 2010 .

[_dfd2e689f73d51b2-10] Maňuch, Patterson, Poon, Thachuk, 2011 .

[_ead36952a24cee6c-11] Garg, Tamassia, 2001 .