Really Straight Graph Drawings
Dujmović, Vida and Suderman, Matthew and Wood, David R. (2004) Really Straight Graph Drawings. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 122-132 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_14).
Full text not available from this repository.
We study straight-line drawings of 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, and that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). Drawings of non-planar graphs with few slopes are also considered. For example, it is proved that graphs of bounded degree and bounded treewidth have drawings with 0(log n) slopes. 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, Feb. 7-13, 2004. Research supported by NSERC and COMBSTRU.
Repository Staff Only: item control page