Separating Thickness from Geometric Thickness

Eppstein, David (2002) Separating Thickness from Geometric Thickness. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 150-161 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_15).

Full text not available from this repository.

Abstract

We show that graph-theoretic thickness and geometric thickness are not asymptotically equivalent: for every t, there exists a graph with thickness three and geometric thickness \ge t.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_15
Classifications:M Methods > M.500 Layered
Z Theory > Z.999 Others
ID Code:297

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. Graph Theory and Theoretical Physics, chapter 4, pp. 139-153. Academic Press, 1967.

L.W. Beineke and F. Harary. The thickness of the complete garph. Canad. J. Math. 17:850-859, 1965.

F. Bernhart and P.C. Kainen. The book thickness of a graph. J. Combinatorial Theory, Ser. B 27(3):320-331, 1979.

M.B. Dillencourt, D. Eppstein, and D.S. Hirschberg. Geometric thickness of complete graphs. J. Graph Algorithms & Applications 4(3):5-17, 2000, arXiv:math.CO/9910185.

D. Eppstein. Separating geometric thickness from book thickness. arXiv.org, September 2001, arXiv:math.CO/0109195.

I. Fáry. On straight line representation of planar graphs. Acta Sci. Math. Szeged. 11:229-233, 1948.

R.L. Graham, B.L. Rothschild, and J.H. Spencer. Ramsey Theory. Wiley, 1980.

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. Selected Topics in Operations Research and Mathematical Economics: Proc. 8th Symp. Operations Research, pp. 315-324. Springer-Verlag, Lecture Notes in Economics and Mathematical Systems 226, August 1983.

P.C. Kainen. Thickness and coarseness of graphs. Abh. Math. Sem. Univ. Hamburg 39:88-95, 1973.

A. Mansfield. Determining the thickness of a graph is NP-hard. Math. Proc. Cambridge Philos. Soc. 93(9):9-23, 1983.

J. Mayer. Decomposition de K_{16} en trois graphes planaire. J. Comb. Th., Ser. B 13:71, 1972.

J. Vasak. The thickness of the complete graph having 6m + 4 points. Manuscript, cited in [9] and [10].

D.R. Wood. Geometric thickness in a grid of linear area. Proc. Euroconf. Combinatorics, Graph Theory, and Applications, pp. 310-315. Univ, Autònoma de Barcelona, Centre de Recerca Matemàtica, September 2001, http://www.cs.usyd.edu.au./~davidw/papers/Wood-COMB01.ps.