Drawing planar graphs of bounded degree with few slopes

Details Drawing planar graphs of bounded degree with few slopes Drawing planar graphs of bounded degree with few slopes

2010-09-07

arxiv.org/abs/1009.1315v2

Mathematics

Combinatorics

Scientific paper

We settle a problem of Dujmovi\'c, Eppstein, Suderman, and Wood by showing that there exists a function $f$ with the property that every planar graph $G$ with maximum degree $d$ admits a drawing with noncrossing straight-line edges, using at most $f(d)$ different slopes. If we allow the edges to be represented by polygonal paths with {\em one} bend, then 2d slopes suffice. Allowing {\em two} bends per edge, every planar graph with maximum degree $d\ge 3$ can be drawn using segments of at most $\lceil d/2\rceil$ different slopes. There is only one exception: the graph formed by the edges of an octahedron is 4-regular, yet it requires 3 slopes. These bounds cannot be improved.

Affiliated with

Also associated with

No associations

Rating

Drawing planar graphs of bounded degree 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 Drawing planar graphs of bounded degree with few slopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Drawing planar graphs of bounded degree with few slopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-704835