|
|||||
|
|
Drawings of planar graphs with few slopes and segments |
|
| Authors: | Vida Dujmovi&#x , David Eppstein, Matthew Suderman,David R. Wood |
| Affiliation: | aDepartment of Mathematics and Statistics, McGill University, Montréal, Canada bDepartment of Computer Science, University of California, Irvine, California, USA cMcGill Centre for Bioinformatics, School of Computer Science, McGill University, Montréal, Canada dDepartament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Barcelona, Spain |
| 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 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. |
| Keywords: | Graph drawing Planar graph Slope Segment Canonical decomposition |
| 本文献已被 ScienceDirect 等数据库收录！ | |