Geometric Thickness of Complete Graphs

Dillencourt, Michael B. and Eppstein, David and Hirschberg, Daniel S. (1998) Geometric Thickness of Complete Graphs. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998, Montréal, Canada , pp. 102-110 (Official URL: http://dx.doi.org/10.1007/3-540-37623-2_8).

Full text not available from this repository.

Abstract

We define the geometric thickness of a graph to be the smallest number of layers such that we can draw the graph in the plane with straight-line edges and assign each edge to a layer so that no two edges on the same layer cross. The geometric thickness lies between two previously studied quantities, the (graph-theoretical) thickness and the book thickness. We investigate the geometric thickness of the family of complete graphs, {K_n} . We show that the geometric thickness of K_n lies between \lceil (n/5.646)+0.342 \rceil and \lceil n/4 \rceil, and we give exact values of the geometric thickness of K_n for n \le 12 and n \in {15,16}.

Item Type:Conference Paper
Additional Information:10.1007/3-540-37623-2_8
Classifications:M Methods > M.999 Others
M Methods > M.500 Layered
G Algorithms and Complexity > G.700 Layering
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered
ID Code:287

Repository Staff Only: item control page

References

V.B. Alekseev and V.S. Goncakov. The thickness of an arbitrary complete graph. Math. USSR Sbornik, 30(2):187-202, 1976.

L.W. Beineke. The decomposition of complete graphs into planar subgraphs. In F. Harary, editor, Graph Theory and Theoretical physics, chapter 4, pages 139-153. Academic Press, London, UK, 1967.

L.W. Beineke and F. Harary. The thickness of the complete graph. Canadian Journal of Mathematics, 17:850-859, 1965.

F. Bernhart and P.C. Kainen. The book thickness of a graph. Journal of Combinatorial Theory Series B, 27:320-331, 1979.

R. Cimikowski. On heuristics for determining the thickness of a graph. Information Sciences, 85:87-98, 1995.

A.M. dean, J.P. Hutchinson, and E.R. Scheinerman. On the thickness and arboricity of a graph. Journal of Combinatorial Theory Series B, 52:147-151, 1991.

J.H. Halton. On the thickness of graphs given degree. Information Sciences, 54:219-238, 1991.

N. Hartsfield and G. Ringel. Pearls in Graph Theory. Academic Press, Boston, MA, 1990.

B. Jackson and G. Ringel. Plane constructions for graphs, networks and maps: Measurements of planarity. In G. Hammer and D. Pallaschke, editors, Selected Topics in Operations Research and Mathematical Economics: Proceedings of the 8th Symposium on Operations Research, pages 315-324, Karlsruhe, West Germany, August 1983. Springer-Verlag Lecture Notes in Economics and Mathematical Systems 226.

P.C. Kainen. Thickness and coarseness of graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 39:88-95, 1973.

A. Mansfield. Determining the thickness of a graph is NP-hard. Mathematical Proceedings of the Cambridge Philosophical Society, 93(9):9-23, 1983.

J. Mayer. Decomposition de K_16 en trois graphes planaries. Journal of Combinatorial Theory Series B, 13:71, 1972.

J. Vasak. The thickness of the complete graph having 6m+4 ponts. Manuscript. Cited in [8,9].