Really Straight Graph Drawings

Dujmovic, 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.

Abstract

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_14
Classifications:P Styles > P.600 Poly-line > P.600.300 Mainly Orthogonal
G Algorithms and Complexity > G.210 Bends
Z Theory > Z.250 Geometry
ID Code:579

Repository Staff Only: item control page

References

Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1-2):1-45, 1998.

Guoli Ding and Bogdan Oporowski. Some results on tree decomposition of graphs. J. Graph Theory, 20(4):481-499, 1995.

Vida Dujmovic, Matthew Suderman, and David R. Wood. Really straight graph drawings. arXiv.org:cs.DM/0405112, 2004.

Vida Dujmovic and David R. Wood. On linear layouts of graphs. Discrete Math. Theor. Comput. Sci., 6(2):339-358, 2004.

Christian A. Duncan, David Eppstein, and Stephen G. Kobourov. The geometric thickness of low degree graphs. In Proc. 20th ACM Symp. on Computational Geometry (SoCG '04), pp.340-346. ACM Press, 2004.

David Eppstein. Dilation-free planar graphs. http://www.ics.uci.edu/~eppstein/junkyard/dilation-free/, 1997.

David Eppstein. Separating thickness from geometric thickness. In János Pach, editor, Towards a Theory of Geometric Graphs, vol. 342 of Contemporary Mathematics, pp. 75-86. Amer. Math. Soc., 2004.

Ashim Garg and Roberto Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput., 31(2):601-625, 2001.

Robert E. Jamison. Few slopes without collinearity. Discrete Math., 60:199-206, 1986.

Goos Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16(1):4-32, 1996.

Seth M. Malitz. Graphs with E edges have pagenumber 0(E). J. Algorithms, 17(1):71-84, 1994.

Md. Saidur Rahman, Takao Nishizeki, and Shubashis Ghosh. Rectangular drawings of planar graphs. J. Algorithms, 50:62-78, 2004.

Matthew Suderman. Pathwidth and layered drawings of trees. Internat. J. Comput. Geom. Appl., 14(3):203-225, 2004.

Peter Ungar. On diagrams representing maps. J. London Math. Soc., 28:336-342, 1953.

Greg A. Wade and Jiang-Hsing Chu. Drawability of complete graphs using a minimal slope set. The Computer Journal, 37(2):139-142, 1994.