Drawings of Planar Graphs with Few Slopes and Segments

Abstract

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/2n$ 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.

This paper is submitted to a journal. A preliminary version appeared as "Really Straight Graph Drawings" in the Graph Drawing 2004 conference. See http://arxiv.org/math/0606446 for a companion paper

References in corpus (2)

• Graph Treewidth and Geometric Thickness Parameters
• Graph Drawings with Few Slopes

Cited by in corpus (8)

• Graph Drawings with Few Slopes
• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• Experimental analysis of the accessibility of drawings with few segments
• Every Large Point Set contains Many Collinear Points or an Empty Pentagon
• Outerplanar graph drawings with few slopes
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• Proximity Drawings of High-Degree Trees
• Upward planar drawings with two slopes