# 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: 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 10.1007/3-540-37623-2_8 M Methods > M.999 OthersM Methods > M.500 LayeredG Algorithms and Complexity > G.700 LayeringP Styles > P.720 Straight-lineZ Theory > Z.250 GeometryG Algorithms and Complexity > G.999 OthersG Algorithms and Complexity > G.420 CrossingsP Styles > P.480 Layered http://gdea.informatik.uni-koeln.de/id/eprint/287

### Actions (login required)

 View Item