Drawings of Planar Graphs with Few Slopes and Segments

Simple item page
dc.creatorDujmovic', Vida
dc.creatorEppstein, David
dc.creatorSuderman, Matthew
dc.creatorWood, David R.
dc.date2006-06-19
dc.date.accessioned2026-07-07T10:01:30Z
dc.date.available2026-07-07T10:01:30Z
dc.descriptionWe 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.
dc.descriptionThis 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
dc.identifierhttps://arxiv.org/abs/math/0606450
dc.identifierhttp://arxiv.org/abs/math/0606450
dc.identifierComputational Geometry: Theory and Applications 38:194-212, 2007
dc.identifierdoi:10.1016/j.comgeo.2006.09.002
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/168649
dc.subjectCombinatorics
dc.titleDrawings of Planar Graphs with Few Slopes and Segments
dc.typetext

Files

Collections

arXiv