Bounded-degree graphs can have arbitrarily large slope numbers (Q2583679): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 08:42, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounded-degree graphs can have arbitrarily large slope numbers |
scientific article |
Statements
Bounded-degree graphs can have arbitrarily large slope numbers (English)
0 references
17 January 2006
0 references
A straight-line or geometric drawing of a graph \(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 though any other point that represents a vertex. The slope number of \(G\) is the smallest number of distinct edge slopes used in a straight-line drawing of \(G\). The authors prove that, for any given integer \(d\geq 5\), there exists an \(n\)-vertex graph of maximum degree \(d\) whose slope number is at least \(n^{1/2-1/(d-2)-o(1)}\). In particular, bounded-degree graphs can have arbitrarily large slope number, solving an open problem posed by \textit{V. Dujmović, M. Suderman} and \textit{D. R. Wood} [Lect. Notes Comput. Sci. 3383, 122--132 (2005; Zbl 1111.68571)], and improving a result by \textit{J. Barát, J. Matoušek} and \textit{D. R. Wood} [Electron. J. Comb. 13, No. 1, Research paper R3 (2006; Zbl 1080.05063)].
0 references
straight-line drawing of graphs
0 references
geometric graphs
0 references
slope number of graphs
0 references
slope number
0 references