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 , pp. 102-110(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item