Slope number: Difference between revisions
Citation bot (talk | contribs) Alter: title. Add: jstor, issue, isbn, s2cid, doi. | Use this bot. Report bugs. | Suggested by Corvus florensis | #UCB_webform 737/2500 |
|||
Line 40: | Line 40: | ||
| url = http://www.combinatorics.org/Volume_13/Abstracts/v13i1r3.html |
| url = http://www.combinatorics.org/Volume_13/Abstracts/v13i1r3.html |
||
| volume = 13 |
| volume = 13 |
||
| year = 2006 |
| year = 2006| doi = 10.37236/1029 |
||
| s2cid = 14447853 |
|||
}}. |
|||
*{{citation |
*{{citation |
||
| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović |
| last1 = Dujmović | first1 = Vida | author1-link = Vida Dujmović |
||
| last2 = Suderman | first2 = Matthew |
| last2 = Suderman | first2 = Matthew |
||
| last3 = Wood | first3 = David R. | author3-link = David Wood (mathematician) |
| last3 = Wood | first3 = David R. | title = Graph Drawing | author3-link = David Wood (mathematician) |
||
| editor-last = Pach | editor-first = János | editor-link = János Pach |
| editor-last = Pach | editor-first = János | editor-link = János Pach |
||
| contribution = Really straight graph drawings |
| contribution = Really straight graph drawings |
||
Line 52: | Line 54: | ||
| publisher = Springer-Verlag |
| publisher = Springer-Verlag |
||
| series = [[Lecture Notes in Computer Science]] |
| series = [[Lecture Notes in Computer Science]] |
||
| title = [[International Symposium on Graph Drawing|Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers]] |
|||
| volume = 3383 |
| volume = 3383 |
||
| year = 2005| arxiv = cs/0405112}}. |
| year = 2005| arxiv = cs/0405112| isbn = 978-3-540-24528-5 | s2cid = 1092042 }}. |
||
*{{citation |
*{{citation |
||
| last1 = Eades | first1 = Peter | author1-link = Peter Eades |
| last1 = Eades | first1 = Peter | author1-link = Peter Eades |
||
| last2 = Hong | first2 = Seok-Hee | author2-link = Seok-Hee Hong |
| last2 = Hong | first2 = Seok-Hee | author2-link = Seok-Hee Hong |
||
| last3 = Poon | first3 = Sheung-Hung |
| last3 = Poon | first3 = Sheung-Hung |
||
| editor1-last = Eppstein | editor1-first = David | editor1-link = David Eppstein |
| title = Graph Drawing | editor1-last = Eppstein | editor1-first = David | editor1-link = David Eppstein |
||
| editor2-last = Gansner | editor2-first = Emden R. |
| editor2-last = Gansner | editor2-first = Emden R. |
||
| contribution = On rectilinear drawing of graphs |
| contribution = On rectilinear drawing of graphs |
||
Line 68: | Line 69: | ||
| publisher = Springer |
| publisher = Springer |
||
| series = Lecture Notes in Computer Science |
| series = Lecture Notes in Computer Science |
||
| title = [[International Symposium on Graph Drawing|Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers]] |
|||
| volume = 5849 |
| volume = 5849 |
||
| year = 2010| doi-access = free |
| isbn = 978-3-642-11804-3 | year = 2010| doi-access = free |
||
}}. |
}}. |
||
*{{citation |
*{{citation |
||
Line 99: | Line 99: | ||
| title = On the computational complexity of upward and rectilinear planarity testing |
| title = On the computational complexity of upward and rectilinear planarity testing |
||
| volume = 31 |
| volume = 31 |
||
| year = 2001 |
| year = 2001| s2cid = 15691098 |
||
}}. |
|||
*{{citation |
*{{citation |
||
| last = Hansen | first = Lowell J. |
| last = Hansen | first = Lowell J. |
||
Line 124: | Line 125: | ||
| title = Planar configurations which determine few slopes |
| title = Planar configurations which determine few slopes |
||
| volume = 16 |
| volume = 16 |
||
| year = 1984 |
| year = 1984| s2cid = 122159215 |
||
}}. |
|||
*{{citation |
*{{citation |
||
| last1 = Keszegh | first1 = Balázs |
| last1 = Keszegh | first1 = Balázs |
||
| last2 = Pach | first2 = János | author2-link = János Pach |
| last2 = Pach | first2 = János | author2-link = János Pach |
||
| last3 = Pálvölgyi | first3 = Dömötör |
| last3 = Pálvölgyi | first3 = Dömötör |
||
| title = Graph Drawing |
|||
| editor1-last = Brandes | editor1-first = Ulrik | editor1-link = Ulrik Brandes |
| editor1-last = Brandes | editor1-first = Ulrik | editor1-link = Ulrik Brandes |
||
| editor2-last = Cornelsen | editor2-first = Sabine |
| editor2-last = Cornelsen | editor2-first = Sabine |
||
Line 138: | Line 141: | ||
| publisher = Springer |
| publisher = Springer |
||
| series = Lecture Notes in Computer Science |
| series = Lecture Notes in Computer Science |
||
| title = [[International Symposium on Graph Drawing|Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers]] |
|||
| volume = 6502 |
| volume = 6502 |
||
| year = 2011| arxiv = 1009.1315 |
| year = 2011| arxiv = 1009.1315| isbn = 978-3-642-18468-0 |
||
}}. |
|||
*{{citation |
*{{citation |
||
| last1 = Keszegh | first1 = Balázs |
| last1 = Keszegh | first1 = Balázs |
||
Line 171: | Line 174: | ||
| last3 = Poon | first3 = Sheung-Hung |
| last3 = Poon | first3 = Sheung-Hung |
||
| last4 = Thachuk | first4 = Chris |
| last4 = Thachuk | first4 = Chris |
||
| title = Graph Drawing |
|||
| editor1-last = Brandes | editor1-first = Ulrik | editor1-link = Ulrik Brandes |
| editor1-last = Brandes | editor1-first = Ulrik | editor1-link = Ulrik Brandes |
||
| editor2-last = Cornelsen | editor2-first = Sabine |
| editor2-last = Cornelsen | editor2-first = Sabine |
||
Line 180: | Line 184: | ||
| publisher = Springer |
| publisher = Springer |
||
| series = Lecture Notes in Computer Science |
| series = Lecture Notes in Computer Science |
||
| title = [[International Symposium on Graph Drawing|Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers]] |
|||
| volume = 6502 |
| volume = 6502 |
||
| year = 2011| hdl = 10281/217381 |
| year = 2011| hdl = 10281/217381 |
||
| isbn = 978-3-642-18468-0 |
|||
| hdl-access = free |
| hdl-access = free |
||
}}. |
}}. |
||
Line 200: | Line 204: | ||
| last1 = Mukkamala | first1 = Padmini |
| last1 = Mukkamala | first1 = Padmini |
||
| last2 = Pálvölgyi | first2 = Dömötör |
| last2 = Pálvölgyi | first2 = Dömötör |
||
| title = Graph Drawing |
|||
| editor1-last = van Kreveld | editor1-first = Marc |
| editor1-last = van Kreveld | editor1-first = Marc |
||
| editor2-last = Speckmann | editor2-first = Bettina | editor2-link = Bettina Speckmann |
| editor2-last = Speckmann | editor2-first = Bettina | editor2-link = Bettina Speckmann |
||
Line 207: | Line 212: | ||
| publisher = Springer |
| publisher = Springer |
||
| series = Lecture Notes in Computer Science |
| series = Lecture Notes in Computer Science |
||
| title = [[International Symposium on Graph Drawing|Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers]] |
|||
| volume = 7034 |
| volume = 7034 |
||
| year = 2012| arxiv = 1106.1973 |
| year = 2012| arxiv = 1106.1973| isbn = 978-3-642-25877-0 |
||
| s2cid = 5800524 |
|||
}}. |
|||
*{{citation |
*{{citation |
||
| last1 = Pach | first1 = János | author1-link = János Pach |
| last1 = Pach | first1 = János | author1-link = János Pach |
||
Line 220: | Line 226: | ||
| url = http://www.combinatorics.org/Volume_13/Abstracts/v13i1n1.html |
| url = http://www.combinatorics.org/Volume_13/Abstracts/v13i1n1.html |
||
| volume = 13 |
| volume = 13 |
||
| year = 2006}}. |
| year = 2006| doi = 10.37236/1139 }}. |
||
*{{citation |
*{{citation |
||
| last1 = Pach | first1 = János | author1-link = János Pach |
| last1 = Pach | first1 = János | author1-link = János Pach |
||
Line 239: | Line 245: | ||
| volume = 77 |
| volume = 77 |
||
| year = 1970 |
| year = 1970 |
||
| issue = 5 |
|||
| doi=10.2307/2317384 |
| doi=10.2307/2317384| jstor = 2317384 |
||
}}. |
|||
*{{citation |
*{{citation |
||
| last1 = Wade | first1 = G. A. |
| last1 = Wade | first1 = G. A. |
Revision as of 22:43, 24 November 2023
In graph drawing and geometric graph theory, the slope number of a graph is the minimum possible number of distinct slopes of edges in a drawing of the graph in which vertices are represented as points in the Euclidean plane and edges are represented as line segments that do not pass through any non-incident vertex.
Complete graphs
Although closely related problems in discrete geometry had been studied earlier, e.g. by Scott (1970) and Jamison (1984), the problem of determining the slope number of a graph was introduced by Wade & Chu (1994), who showed that the slope number of an n-vertex complete graph Kn is exactly n. A drawing with this slope number may be formed by placing the vertices of the graph on a regular polygon.
Relation to degree
The slope number of a graph of maximum degree d is clearly at least , because at most two of the incident edges at a degree-d vertex can share a slope. More precisely, the slope number is at least equal to the linear arboricity of the graph, since the edges of a single slope must form a linear forest, and the linear arboricity in turn is at least .
There exist graphs with maximum degree five that have arbitrarily large slope number.[1] However, every graph of maximum degree three has slope number at most four;[2] the result of Wade & Chu (1994) for the complete graph K4 shows that this is tight. Not every set of four slopes is suitable for drawing all degree-3 graphs: a set of slopes is suitable for this purpose if and only if it forms the slopes of the sides and diagonals of a parallelogram. In particular, any degree 3 graph can be drawn so that its edges are either axis-parallel or parallel to the main diagonals of the integer lattice.[3] It is not known whether graphs of maximum degree four have bounded or unbounded slope number.[4]
Planar graphs
As Keszegh, Pach & Pálvölgyi (2011) showed, every planar graph has a planar straight-line drawing in which the number of distinct slopes is a function of the degree of the graph. Their proof follows a construction of Malitz & Papakostas (1994) for bounding the angular resolution of planar graphs as a function of degree, by completing the graph to a maximal planar graph without increasing its degree by more than a constant factor, and applying the circle packing theorem to represent this augmented graph as a collection of tangent circles. If the degree of the initial graph is bounded, the ratio between the radii of adjacent circles in the packing will also be bounded by the ring lemma,[5] which in turn implies that using a quadtree to place each graph vertex on a point within its circle will produce slopes that are ratios of small integers. The number of distinct slopes produced by this construction is exponential in the degree of the graph.
Complexity
It is NP-complete to determine whether a graph has slope number two.[6] From this, it follows that it is NP-hard to determine the slope number of an arbitrary graph, or to approximate it with an approximation ratio better than 3/2.
It is also NP-complete to determine whether a planar graph has a planar drawing with slope number two,[7] and hard for the existential theory of the reals to determine the minimum slope number of a planar drawing.[8]
Notes
- ^ Proved independently by Barát, Matoušek & Wood (2006) and Pach & Pálvölgyi (2006), solving a problem posed by Dujmović, Suderman & Wood (2005). See theorems 5.1 and 5.2 of Pach & Sharir (2009).
- ^ Mukkamala & Szegedy (2009), improving an earlier result of Keszegh et al. (2008); theorem 5.3 of Pach & Sharir (2009).
- ^ Mukkamala & Pálvölgyi (2012).
- ^ Pach & Sharir (2009).
- ^ Hansen (1988).
- ^ Formann et al. (1993); Eades, Hong & Poon (2010); Maňuch et al. (2011).
- ^ Garg & Tamassia (2001).
- ^ Hoffmann (2016).
References
- Barát, János; Matoušek, Jiří; Wood, David R. (2006), "Bounded-degree graphs have arbitrarily large geometric thickness", Electronic Journal of Combinatorics, 13 (1): R3, doi:10.37236/1029, MR 2200531, S2CID 14447853.
- Dujmović, Vida; Suderman, Matthew; Wood, David R. (2005), "Really straight graph drawings", in Pach, János (ed.), Graph Drawing, Lecture Notes in Computer Science, vol. 3383, Berlin: Springer-Verlag, pp. 122–132, arXiv:cs/0405112, doi:10.1007/978-3-540-31843-9_14, ISBN 978-3-540-24528-5, S2CID 1092042.
- Eades, Peter; Hong, Seok-Hee; Poon, Sheung-Hung (2010), "On rectilinear drawing of graphs", in Eppstein, David; Gansner, Emden R. (eds.), Graph Drawing, Lecture Notes in Computer Science, vol. 5849, Berlin: Springer, pp. 232–243, doi:10.1007/978-3-642-11805-0_23, ISBN 978-3-642-11804-3, MR 2680455.
- Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing, 22 (5): 1035–1052, doi:10.1137/0222063, MR 1237161.
- Garg, Ashim; Tamassia, Roberto (2001), "On the computational complexity of upward and rectilinear planarity testing", SIAM Journal on Computing, 31 (2): 601–625, doi:10.1137/S0097539794277123, MR 1861292, S2CID 15691098.
- Hansen, Lowell J. (1988), "On the Rodin and Sullivan ring lemma", Complex Variables, Theory and Application, 10 (1): 23–30, doi:10.1080/17476938808814284, MR 0946096.
- Hoffmann, Udo (2016), "The planar slope number", Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016).
- Jamison, Robert E. (1984), "Planar configurations which determine few slopes", Geometriae Dedicata, 16 (1): 17–34, doi:10.1007/BF00147419, MR 0757792, S2CID 122159215.
- Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör (2011), "Drawing planar graphs of bounded degree with few slopes", in Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing, Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 293–304, arXiv:1009.1315, doi:10.1007/978-3-642-18469-7_27, ISBN 978-3-642-18468-0, MR 2781274.
- Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör; Tóth, Géza (2008), "Drawing cubic graphs with at most five slopes", Computational Geometry: Theory and Applications, 40 (2): 138–147, doi:10.1016/j.comgeo.2007.05.003, MR 2400539.
- Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs", SIAM Journal on Discrete Mathematics, 7 (2): 172–183, doi:10.1137/S0895480193242931, MR 1271989.
- Maňuch, Ján; Patterson, Murray; Poon, Sheung-Hung; Thachuk, Chris (2011), "Complexity of finding non-planar rectilinear drawings of graphs", in Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing, Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 305–316, doi:10.1007/978-3-642-18469-7_28, hdl:10281/217381, ISBN 978-3-642-18468-0, MR 2781275.
- Mukkamala, Padmini; Szegedy, Mario (2009), "Geometric representation of cubic graphs with four directions", Computational Geometry: Theory and Applications, 42 (9): 842–851, doi:10.1016/j.comgeo.2009.01.005, MR 2543806.
- Mukkamala, Padmini; Pálvölgyi, Dömötör (2012), "Drawing cubic graphs with the four basic slopes", in van Kreveld, Marc; Speckmann, Bettina (eds.), Graph Drawing, Lecture Notes in Computer Science, vol. 7034, Springer, pp. 254–265, arXiv:1106.1973, doi:10.1007/978-3-642-25878-7_25, ISBN 978-3-642-25877-0, S2CID 5800524.
- Pach, János; Pálvölgyi, Dömötör (2006), "Bounded-degree graphs can have arbitrarily large slope numbers", Electronic Journal of Combinatorics, 13 (1): N1, doi:10.37236/1139, MR 2200545.
- Pach, János; Sharir, Micha (2009), "5.5 Angular resolution and slopes", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127.
- Scott, P. R. (1970), "On the sets of directions determined by n points", American Mathematical Monthly, 77 (5): 502–505, doi:10.2307/2317384, JSTOR 2317384, MR 0262933.
- Wade, G. A.; Chu, J.-H. (1994), "Drawability of complete graphs using a minimal slope set", The Computer Journal, 37 (2): 139–142, doi:10.1093/comjnl/37.2.139.