Drawing Cubic Graphs with the Four Basic Slopes

Mukkamala, Padmini and Pálvölgyi, Dömötör (2012) Drawing Cubic Graphs with the Four Basic Slopes. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 254-265 (Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_25).

Full text not available from this repository.

Abstract

We show that every cubic graph can be drawn in the plane with straight-line edges using only the four basic slopes, {0, π/4, π/2, 3π/4}. We also prove that four slopes have this property if and only if we can draw K4 with them.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_25
Classifications:P Styles > P.999 Others
ID Code:1260

Repository Staff Only: item control page

References

http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html

http://en.wikipedia.org/wiki/Tableofsimplecubicgraphs

Ambrus, G., Barát, J.: A contribution to queens graphs: A substitution method. Discrete Mathematics 306(12), 1105–1114 (2006)

Ambrus, G., Barát, J., Hajnal, P.: The slope parameter of graphs. Acta Sci. Math (Szeged) 72, 875–889 (2006)

Angelini, P., Cittadini, L., Di Battista, G., Didimo, W., Frati, F., Kaufmann, M., Symvonis, A.: On the Perspectives Opened By Right Angle Crossing Drawings. In:

Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 21–32. Springer, Heidelberg (2010)

Arikushi, K., Fulek, R., Keszegh, B., Morić F., Tóth, C.D.: Graphs that Admit Right Angle Crossing Drawings. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 135–146. Springer, Heidelberg (2010)

Barát, J., Matousek, J., Wood, D.R.: Bounded-degree graphs have arbitrarily large geometric thickness. Electr. J. Comb. 13(1) (2006)

Bell, J., Stevens, B.: A survey of known results and research areas for n-queens. Discrete Mathematics 309, 1–31 (2009)

Didimo, W., Eades, P., Liotta, G.: Drawing Graphs With Right Angle Crossings. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 206–217. Springer, Heidelberg (2009)

Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algorithms Appl. 4(3), 5–17 (2000)

Dujmović, V., Eppstein, D., Suderman, M., Wood, D.R.: Drawings of planar graphs with few slopes and segments. Comput. Geom. 38(3), 194–212 (2007)

Dujmović , V., Suderman, M., Wood, D.R.: Really Straight Graph Drawings. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 122–132. Springer, Heidelberg (2005)

Dujmovic, V., Wood, D.R.: Graph treewidth and geometric thickness parameters. Discrete & Computational Geometry 37(4), 641–670 (2007)

Duncan, C.A., Eppstein, D., Kobourov, S.G.: The geometric thickness of low degree graphs. In: Snoeyink, J., Boissonnat, J.-D. (eds.) Symposium on Computational Geometry, pp. 340–346. ACM (2004)

Engelstein, M.: Drawing graphs with few slopes. Intel Competition for high school students (2005)

Eppstein, D.: Separating Thickness From Geometric Thickness. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 150–161. Springer, Heidelberg (2002)

Hutchinson, J.P., Shermer, T.C., Vince, A.: On representations of some thickness-two graphs. Comput. Geom. 13(3), 161–171 (1999)

Jelínek, V., Jelínková, E., Kratochvíl, J., Lidický, B., Tesař , M., Vyskočil, T.: The Planar Slope Number Of Planar Partial 3-Trees Of Bounded Degree. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 304–315. Springer, Heidelberg (2010)

Kainen, P.C.: Thickness and coarseness of graphs. Abh. Math. Sem. Univ. Hamburg 39, 88–95 (1973)

Keszegh, B., Pach, J., Pálvölgyi, D.: Drawing Planar Graphs of Bounded Degree With Few Slopes. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 293–304. Springer, Heidelberg (2011)

Keszegh, B., Pach, J., Pálvölgyi, D., Tóth , G.: Drawing cubic graphs with at most five slopes. Comput. Geom. 40(2), 138–147 (2008)

Keszegh, B., Pach, J., Pálvölgyi, D., Tóth, G.: Cubic graphs have bounded slope parameter. J. Graph Algorithms Appl. 14(1), 5–17 (2010)

Meringer, M.: Fast generation of regular graphs and construction of cages. J. Graph Theory 30, 137–146 (1999)

Mukkamala, P.: Obstacles, Slopes and Tic-Tac-Toe: An excursion in discrete geomety and combinatorial game theory. PhD thesis, Rutgers, The State University of New Jersey (2011), http://arxiv.org/abs/1106.1973

Mukkamala, P., Pálvölgyi, D.: Drawing cubic graphs with the four basic slopes. CoRR, abs/1106.1973 (2011)

Mukkamala, P., Szegedy, M.: Geometric representation of cubic graphs with four directions. Comput. Geom. 42(9), 842–851 (2009)

Mutzel, P., Odenthal, T., Scharbrodt, M.: The thickness of graphs: A survey. Graphs Combin. 14, 59–73 (1998)

Pach, J., Pálvölgyi, D.: Bounded-degree graphs can have arbitrarily large slope numbers. Electr. J. Comb. 13(1) (2006)

Wade, G.A., Chu, J.-H.: Drawability of complete graphs using a minimal slope set. Comput. J. 37(2), 139–142 (1994)