Drawings of planar graphs with few slopes and segments期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Drawings of planar graphs with few slopes and segments

Authors:	Vida Dujmovi&#x; David Eppstein Matthew Suderman David R Wood

Institution:	^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 等数据库收录！