Geometric Thickness of Complete Graphs
(1998) Geometric Thickness of Complete Graphs. In Whitesides, Sue H., Eds. Proceedings Graph Drawing, pages pp. 102-110, Montréal, Canada.
Full text of this item is not available.
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}.
| Display Formats: | BibTex |
|---|---|
| EPrint Type: | Conference Paper |
| Subjects: | 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 |
| Deposited By: | Arnopolina, Galina |
| Deposited On: | 09 November 2004 |
| Alternative Locations: | http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1547&spage=102 |