Graph drawings with few slopes

DOI10.1016/J.COMGEO.2006.08.002MaRDI QIDQ2385698zbMATH OpenOpenAlexFDO

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

Publication date 12 October 2007

Published in Computational Geometry (Search for Journal in Brave)

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

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)

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.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 1375581 (Why is no real title available?)
• scientific article; zbMATH DE number 1944139 (Why is no real title available?)
• scientific article; zbMATH DE number 2145231 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 4121438 (Why is no real title available?)
• scientific article; zbMATH DE number 3305808 (Why is no real title available?)
• 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
• Bounded-degree graphs have arbitrarily large geometric thickness
• Level-planar drawings with few slopes
• Distinct distances in graph drawings
• On tree-partition-width
• Drawing outer 1-planar graphs with few slopes
• 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
• A note on isosceles planar graph drawing
• Level-planar drawings with few slopes
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Cubic Graphs Have Bounded Slope Parameter
• Lower against number in graphs
• The planar slope number of planar partial 3-trees of bounded degree
• Graph Drawing
• Drawing outer 1-planar graphs with few slopes
• Upward Planar Drawings with Three and More Slopes
• Universal slope sets for upward planar drawings
• On the complexity of the planar slope number problem

Describes a project that uses

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)