Bounded-degree graphs can have arbitrarily large slope numbers
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)].
- Bounded-degree graphs have arbitrarily large geometric thickness
- Bounded-degree graphs have arbitrarily large queue-number
- Extremal size in graphs with bounded degree.
- Bounded degrees and prescribed distances in graphs
- Regular graphs of large girth and arbitrary degree
- Graphs with maximum size and lower bounded girth
- Distinguishing infinite graphs with bounded degrees
- On the number of connected sets in bounded degree graphs
- On the Number of Connected Sets in Bounded Degree Graphs
- Extremal graphs with bounded vertex bipartiteness number
- Drawing subcubic planar graphs with four slopes and optimal angular resolution
- Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
- Upward planar drawings with three and more slopes
- Graph drawings with few slopes
- Drawings of planar graphs with few slopes and segments
- Outerplanar graph drawings with few slopes
- Drawing cubic graphs with at most five slopes
- Bounded-degree graphs have arbitrarily large geometric thickness
- Drawing partial 2-trees with few slopes
- On the complexity of the planar slope number problem
- Drawing Cubic Graphs with the Four Basic Slopes
- The planar slope number of planar partial 3-trees of bounded degree
- Cubic Graphs Have Bounded Slope Parameter
- Crossings in grid drawings
- Upward planar drawings with two slopes
- Drawing subcubic 1-planar graphs with few bends, few slopes, and large angles
- Upward Planar Drawings with Three and More Slopes
- Level-planar drawings with few slopes
- Level-planar drawings with few slopes
- Planar drawings with few slopes of Halin graphs and nested pseudotrees
- Bounds on the crossing resolution of complete geometric graphs
- Planar drawings with few slopes of Halin graphs and nested pseudotrees
- Geometric representation of cubic graphs with four directions
This page was built for publication: Bounded-degree graphs can have arbitrarily large slope numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583679)
