2006/06/19 by Vida Dujmović, Vida Dujmovic', Matthew Suderman +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.1016/j.comgeo.2006.08.002
published as Computational Geometry: Theory and Applications 38:181-193, 2007 · This paper is submitted to a journal. A preliminary version appeared as "Really Straight Graph Drawings" in the Graph Drawing 2004 conference. Also see our companion paper (http://arxiv.org/abs/math/0606450)
arxiv created 2006/06/19 · openalex publication_date 2006/09/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
The "slope-number" of a graph G is the minimum number of distinct edge slopes in a straight-line drawing of G in the plane. We prove that for Δ≥5 and all large n, there is a Δ-regular n-vertex graph with slope-number at least n1-(8+ε)/(Δ+4). This is the best known lower bound on the slope-number of a graph with bounded degree. We prove upper and lower bounds on the slope-number of complete bipartite graphs. We prove a general upper bound on the slope-number of an arbitrary graph in terms of its bandwidth. It follows that the slope-number of interval graphs, cocomparability graphs, and AT-free graphs is at most a function of the maximum degree. We prove that graphs of bounded degree and bounded treewidth have slope-number at most O(log n). Finally we prove that every graph has a drawing with one bend per edge, in which the number of slopes is at most one more than the maximum degree. In a companion paper (http://arxiv.org/abs/math/0606450), planar drawings of graphs with few slopes are also considered.