Graph Drawings with Few Slopes

Details Graph Drawings with Few Slopes Graph Drawings with Few Slopes

2006-06-19

arxiv.org/abs/math/0606446v1

Computational Geometry: Theory and Applications 38:181-193, 2007

Mathematics

Combinatorics

This paper is submitted to a journal. A preliminary version appeared as "Really Straight Graph Drawings" in the Graph Drawing

Scientific paper

10.1016/j.comgeo.2006.08.002

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 $\Delta\geq5$ and all large $n$, there is a $\Delta$-regular $n$-vertex graph with slope-number at least $n^{1-\frac{8+\epsilon}{\Delta+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.

Affiliated with

Also associated with

No associations

Rating

Graph Drawings with Few Slopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Drawings with Few Slopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Drawings with Few Slopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-304952