Graph Treewidth and Geometric Thickness Parameters

Preprint English OPEN
Dujmović, Vida; Wood, David R.;
(2005)

Consider a drawing of a graph $G$ in the plane such that crossing edges are coloured differently. The minimum number of colours, taken over all drawings of $G$, is the classical graph parameter "thickness". By restricting the edges to be straight, we obtain the "geometr... View more
  • References (72)
    72 references, page 1 of 8

    [1] Jin Akiyama and Mikio Kano. Path factors of a graph. In Graphs and applications, pp. 1-21. Wiley, 1985.

    [2] V. B. Alekseev and V. S. Gonchakov. Thickness of arbitrary complete graphs. Mat. Sbornik, 101:212-230, 1976.

    [3] I. Algor and Noga Alon. The star arboricity of graphs. Discrete Math., 75(1- 3):11-22, 1989.

    [4] Noga Alon, Colin McDiarmid, and Bruce Reed. Star arboricity. Combinatorica, 12(4):375-380, 1992.

    [5] Yasukazu Aoki. The star-arboricity of the complete regular multipartite graphs. Discrete Math., 81(2):115-122, 1990.

    [6] Dan Archdeacon. The geometric thickness of the complete graph, 2003. http://www.emba.uvm.edu/∼{}archdeac/problems/geomthick.html.

    [7] Kouhei Asano. On the genus and thickness of graphs. J. Combin. Theory Ser. B, 43(3):287-292, 1987.

    [8] Kouhei Asano. On the thickness of graphs with genus 2. Ars Combin., 38:87-95, 1994.

    [9] Ja´nos Bara´t, Jirˇ´ı Matouˇsek, and David R. Wood. Bounded-degree graphs have arbitrarily large geometric thickness. Electron. J. Combin., 13(1):R3, 2006.

    [10] Lowell W. Beineke. The decomposition of complete graphs into planar subgraphs. In Frank Harary, ed., Graph Theory and Theoretical Physics, pp. 139- 154. Academic Press, 1967.

  • Metrics
Share - Bookmark