Geometric Thickness of Complete GraphsDillencourt, Michael B. and Eppstein, David and Hirschberg, Daniel S. (1998) Geometric Thickness of Complete Graphs. In: Graph Drawing 6th International Symposium, GD’ 98, August 1315, 1998 , pp. 102110(Official URL: http://dx.doi.org/10.1007/3540376232_8). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540376232_8
AbstractWe 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 straightline 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 (graphtheoretical) 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}.
Actions (login required)
