Graph drawings with few slopes

DOI10.1016/J.COMGEO.2006.08.002zbMATH Open1128.65020OpenAlexW1998148652MaRDI QIDQ2385698FDOQ2385698

Authors: Matthew Suderman, David R. Wood, Vida Dujmović 

Publication date: 12 October 2007

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: 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 $Deltageq5$ and all large $n$, there is a $Delta$-regular $n$-vertex graph with slope-number at least $n^{1-frac8+epsilonDelta+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(logn)$. 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.

Full work available at URL: https://arxiv.org/abs/math/0606446

Recommendations

• Bounded-degree graphs can have arbitrarily large slope numbers
• Graph Drawing

zbMATH Keywords

complete multipartite graphgraph drawingslopeconvex slope-numberslope-number

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 2N noncollinear points determine at least 2N directions
• A note on caterpillar-embeddings with no two parallel edges
• A note on the minimum number of edge-directions of a convex polytope
• A partial k-arboretum of graphs with bounded treewidth
• Bounded-degree graphs can have arbitrarily large slope numbers
• Bounded-degree graphs have arbitrarily large geometric thickness
• Characterisations of intersection graphs by vertex orderings
• Concept Lattices
• Crooked diagrams with few slopes
• Direction trees
• Drawability of Complete Graphs Using a Minimal Slope Set
• Drawing orders with few slopes
• Drawings of planar graphs with few slopes and segments
• Few slopes without collinearity
• Geometric Thickness of Complete Graphs
• Graph Drawing
• Graph Drawing
• Graphs with E Edges Have Pagenumber O(√E)
• Interval degree and bandwidth of a graph
• Lattice diagrams with few slopes
• On the Sets of Directions Determined by n Points
• On the number of directions determined by a three-dimensional points set
• PATHWIDTH AND LAYERED DRAWINGS OF TREES
• Planar configurations which determine few slopes
• Solution of Scott's problem on the number of directions determined by a point set in 3-space
• Some results on tree decomposition of graphs
• Structure of slope-critical configurations
• The asymptotic number of labeled graphs with given degree sequences
• The complexity of finding uniform emulations on paths and ring networks
• The geometric thickness of low degree graphs

Cited In (26)

• Universal slope sets for 1-bend planar drawings
• Drawing cubic graphs with at most five slopes
• Drawing Graphs with Few Arcs
• Product structure of graph classes with bounded treewidth
• Drawings of planar graphs with few slopes and segments
• Level-planar drawings with few slopes
• Bounded-degree graphs have arbitrarily large geometric thickness
• Distinct distances in graph drawings
• Drawing outer 1-planar graphs with few slopes
• On tree-partition-width
• Drawing Cubic Graphs with the Four Basic Slopes
• NP-completeness of slope-constrained drawing of complete graphs
• Outerplanar graph drawings with few slopes
• Upward planar drawings with three and more slopes
• Tree-partitions with bounded degree trees
• Level-planar drawings with few slopes
• A note on isosceles planar graph drawing
• Cubic Graphs Have Bounded Slope Parameter
• Lower against number in graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Graph Drawing
• Drawing outer 1-planar graphs with few slopes
• The planar slope number of planar partial 3-trees of bounded degree
• Upward Planar Drawings with Three and More Slopes
• Universal slope sets for upward planar drawings
• On the complexity of the planar slope number problem

Uses Software

• LatDraw

This page was built for publication: Graph drawings with few slopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2385698)