publication . Book . Other literature type . Preprint . Part of book or chapter of book . Article . 2007

Graph Treewidth and Geometric Thickness Parameters

Dujmović, V.; David Wood;
  • Published: 01 May 2007
Abstract
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 "geometric thickness". By further restricting the vertices to be in convex position, we obtain the "book thickness". This paper studies the relationship between these parameters and treewidth. Our first main result states that for graphs of treewidth $k$, the maximum thickness and the maximum geometric thickness both equal $\lceil{k/2}\rceil$. This says that the lower bound for thickness can be matched by...
Subjects
free text keywords: Mathematics - Combinatorics, 05C62, Combinatorics, General position, Vertex (geometry), Complete graph, Discrete mathematics, Planar graph, symbols.namesake, symbols, Convex position, Outerplanar graph, Treewidth, Mathematics, Arboricity, Conjecture, 1-planar graph, Graph, Upper and lower bounds
Funded by
NSERC
Project
  • Funder: Natural Sciences and Engineering Research Council of Canada (NSERC)
72 references, page 1 of 5

[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. [OpenAIRE]

[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. [OpenAIRE]

[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. [OpenAIRE]

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

[11] Lowell W. Beineke and Frank Harary. The thickness of the complete graph. Canad. J. Math., 17:850-859, 1965.

[12] Lowell W. Beineke, Frank Harary, and J. W. Moon. On the thickness of the complete bipartite graph. Proc. Cambridge Philos. Soc., 60(1):1-5, 1964. [OpenAIRE]

[13] Frank R. Bernhart and Paul C. Kainen. The book thickness of a graph. J. Combin. Theory Ser. B, 27(3):320-331, 1979. [OpenAIRE]

[14] Robin Blankenship. Book Embeddings of Graphs. Ph.D. thesis, Department of Mathematics, Louisiana State University, U.S.A., 2003.

[15] Robin Blankenship and Bogdan Oporowski. Book embeddings of graphs and minor-closed classes. In Proc. 32nd Southeastern International Conf. on Combinatorics, Graph Theory and Computing. Department of Mathematics, Louisiana State University, 2001.

72 references, page 1 of 5
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Book . Other literature type . Preprint . Part of book or chapter of book . Article . 2007

Graph Treewidth and Geometric Thickness Parameters

Dujmović, V.; David Wood;