Really Straight Drawings I : Planar Graphs ∗

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 5n/2 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. †School of Computer Science, Carleton University, Ottawa, Ontario, Canada (vida@scs.carleton.ca). Supported by NSERC. ‡Department of Computer Science, University of California, Irvine, California, U.S.A. (eppstein@ics.uci.edu). §School of Computer Science, McGill University, Montréal, Québec, Canada (msuder@cs.mcgill.ca). Supported by NSERC. ¶Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Catalunya, Spain (david.wood@upc.edu). Supported by the Government of Spain grant MEC SB2003-0270. ∗A preliminary version of this paper was published in the Proceedings of the 12th International Symposium on Graph Drawing (GD ’04), Lecture Notes in Computer Science 3383:122–132, Springer, 2004. Research initiated at the International Workshop on Fixed Parameter Tractability in Geometry and Games, organised by Sue Whitesides; Bellairs Research Institute of McGill University, Holetown, Barbados, February 7–13, 2004.