Jump to content

Slope number: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
m Planar graphs: move image up a little
m References: more authorlinks
Line 26: Line 26:
*{{citation
*{{citation
| last1 = Barát | first1 = János
| last1 = Barát | first1 = János
| last2 = Matoušek | first2 = Jiří
| last2 = Matoušek | first2 = Jiří | author2-link = Jiří Matoušek (mathematician)
| last3 = Wood | first3 = David R.
| last3 = Wood | first3 = David R.
| issue = 1
| issue = 1
| journal = Electronic Journal of Combinatorics
| journal = [[Electronic Journal of Combinatorics]]
| mr = 2200531
| mr = 2200531
| page = R3
| page = R3
Line 51: Line 51:
| year = 2005}}.
| year = 2005}}.
*{{citation
*{{citation
| last1 = Eades | first1 = Peter
| last1 = Eades | first1 = Peter | author1-link = Peter Eades
| last2 = Hong | first2 = Seok-Hee
| last2 = Hong | first2 = Seok-Hee
| last3 = Poon | first3 = Sheung-Hung
| last3 = Poon | first3 = Sheung-Hung
Line 63: Line 63:
| publisher = Springer
| publisher = Springer
| series = Lecture Notes in Computer Science
| series = Lecture Notes in Computer Science
| title = Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers
| 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}}.
| year = 2010}}.
Line 85: Line 85:
*{{citation
*{{citation
| last1 = Garg | first1 = Ashim
| last1 = Garg | first1 = Ashim
| last2 = Tamassia | first2 = Roberto
| last2 = Tamassia | first2 = Roberto | author2-link = Roberto Tamassia
| doi = 10.1137/S0097539794277123
| doi = 10.1137/S0097539794277123
| issue = 2
| issue = 2
| journal = SIAM Journal on Computing
| journal = [[SIAM Journal on Computing]]
| mr = 1861292
| mr = 1861292
| pages = 601–625
| pages = 601–625
Line 97: Line 97:
| last = Hansen | first = Lowell J.
| last = Hansen | first = Lowell J.
| issue = 1
| issue = 1
| journal = Complex Variables. Theory and Application. An International Journal
| journal = Complex Variables, Theory and Application
| mr = 946096
| mr = 946096
| pages = 23–30
| pages = 23–30
Line 116: Line 116:
| publisher = Springer
| publisher = Springer
| series = Lecture Notes in Computer Science
| series = Lecture Notes in Computer Science
| title = Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers
| 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}}.
| year = 2011}}.
Line 157: Line 157:
| publisher = Springer
| publisher = Springer
| series = Lecture Notes in Computer Science
| series = Lecture Notes in Computer Science
| title = Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers
| 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}}.
| year = 2011}}.
Line 172: Line 172:
| year = 2009}}.
| year = 2009}}.
*{{citation
*{{citation
| last1 = Pach | first1 = János
| last1 = Pach | first1 = János | author1-link = János Pach
| last2 = Pálvölgyi | first2 = Dömötör
| last2 = Pálvölgyi | first2 = Dömötör
| issue = 1
| issue = 1
| journal = Electronic Journal of Combinatorics
| journal = [[Electronic Journal of Combinatorics]]
| mr = 2200545
| mr = 2200545
| page = N1
| page = N1

Revision as of 00:27, 26 July 2012

A drawing of the Petersen graph with slope number 3

In graph drawing, 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

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 most 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 most .

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. It is not known whether graphs of maximum degree four have bounded or unbounded slope number.[3]

The method of Keszegh, Pach & Pálvölgyi (2011) for combining circle packings and quadtrees to achieve bounded slope number for planar graphs with bounded degree

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,[4] 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.[5] 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.[6]

Notes

References