Drawings of Planar Graphs with Few Slopes and Segments

Details Drawings of Planar Graphs with Few Slopes and Segments Drawings of Planar Graphs with Few Slopes and Segments

2006-06-19

arxiv.org/abs/math/0606450v1

Computational Geometry: Theory and Applications 38:194-212, 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.09.002

We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on $n$ vertices has a plane drawing with at most ${5/2}n$ segments and at most $2n$ slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered.

Affiliated with

Also associated with

No associations

Rating

Drawings of Planar Graphs with Few Slopes and Segments 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 Drawings of Planar Graphs with Few Slopes and Segments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Drawings of Planar Graphs with Few Slopes and Segments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-304963