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 , 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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1489

Actions (login required)

View Item