EPrints .org
Home || About || Browse || Search || Register || User Area || Help

Separating Thickness from Geometric Thickness

Eppstein, David (2002) Separating Thickness from Geometric Thickness. In Goodrich, Michael T. and Kobourov, Stephen G., Eds. Proceedings Graph Drawing, pages pp. 150-161, Irvine, CA, USA.

Full text of this item is not available.

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.

Display Formats:BibTex
EPrint Type:Conference Paper
Subjects:M Methods > M.500 Layered
Z Theory > Z.999 Others
ID Code:297
Deposited By:Martinez Leon, Victoria
Deposited On:01 December 2004
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2528&spage=150

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.


Site Administrator: gdea@informatik.uni-koeln.de