Logo

Login | Create Account

Separating Thickness from Geometric Thickness

Eppstein, David (2002) Separating Thickness from Geometric Thickness. [Conference Paper]

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
Classifications:M Methods > M.500 Layered
Z Theory > Z.999 Others
ID Code:297
Deposited By:Martinez Leon, Victoria
Deposited On:01 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2528&spage=150

Repository Staff Only: item control page

References

1. V.B. Alekseev and V.S. Goncakov. The thickness of an arbitrary complete graph. Math USSR Sbornik 30(2):187-202, 1976.

2. L.W. Beineke. The decomposition of complete graphs into planar subgraphs. Graph Theory and Theoretical Physics, chapter 4, pp. 139-153. Academic Press, 1967.

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

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

5. 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.

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

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

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

9. N. Hartsfield and G. Ringel. Pearls in Graph Theory. Academic Press, Boston, MA, 1990.

10. 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.

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

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

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

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

15. 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.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.