Maximizing the Degree of (Geometric) Thickness-t Regular Graphs

Duncan, Christian A. (2015) Maximizing the Degree of (Geometric) Thickness-t Regular Graphs. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015, Los Angeles, CA, USA , pp. 199-204 (Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_17).

Full text not available from this repository.

Abstract

In this paper, we show that there exist (6t−1)-regular graphs with thickness t, by constructing such an example graph. Since all graphs of thickness t must have at least one node with degree less than 6t, this construction is optimal. We also show, by construction, that there exist 5t-regular graphs with geometric thickness at most t. Our construction for the latter builds off of a relationship between geometric thickness and the Cartesian product of two graphs.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.540 Planar
P Styles > P.720 Straight-line
Z Theory > Z.999 Others
ID Code:1489

Repository Staff Only: item control page

References

Battle, J., Harary, F., Kodama, Y.: Every planar graph with nine points has a nonplanar complement. Bull. Amer. Math. Soc. 68(6), 569–571 (1962). http://​dx.​doi.​org/​10.​1090/​S0002-9904-1962-10850-7

Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algorithms Appl. 4(3), 5–17 (2000). http://​dx.​doi.​org/​10.​7155/​jgaa.​00023

Durocher, S., Gethner, E., Mondal, D.: Thickness and colorability of geometric graphs. In: Brandstädt, A., Jansen, K., Reischuk, R. (eds.) WG 2013. LNCS, vol. 8165, pp. 237–248. Springer, Heidelberg (2013)

Harary, F.: Research problem. Bull. Amer. Math. Soc. 67, 542 (1961)

Kainen, P.: Thickness and coarseness of graphs. Abh. aus dem Mathematischen Semin. der Univ. Hamburg 39(1), 88–95 (1973). http://​dx.​doi.​org/​10.​1007/​BF02992822

Mutzel, P., Odenthal, T., Scharbrodt, M.: The thickness of graphs: a survey. Graphs Comb. 14(1), 59–73 (1998). http://​dx.​doi.​org/​10.​1007/​PL00007219

Tutte, W.T.: The non-biplanar character of the complete 9-graph. Can. Math. Bull. 6(3), 319–330 (1963)

Tutte, W.T.: The thickness of a graph. Indagationes Math. 25, 567–577 (1963)