Graph Treewidth and Geometric Thickness Parameters

Dujmovic, Vida and Wood, David R. (2006) Graph Treewidth and Geometric Thickness Parameters. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 129-140 (Official URL: http://dx.doi.org/10.1007/11618058_13).

Full text not available from this repository.

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 t(G). By restricting the edges to be straight, we obtain the geometric thickness gt(G). By further restricting the vertices to be in convex position, we obtain the book thickness _t(G). This paper studies the relationship between these parameters and the treewidth of G. Let T_k denote the class of graphs with treewidth at most k. Let t{T_k} / gt{T_k} / _t{T_k} denote the maximum thickness / geometric thickness / book thickness of a graph in T_k. We prove that : t{T_k}=gt{T_k}=ceil{k/2}, and _t{T_k}=k for k<=2, and _t{T_k}=k+1 for k>=3. The first result says that the lower bound for thickness can be matched by an upper bound, even in the more restrictive geometric setting. The second result disproves the conjecture of Ganley and Heath [Discrete Appl. Math. 2001] that _t{T_k}=k for all k. Analogous results are proved for outerthickness, arboricity, and star-arboricity.

Item Type:Conference Paper
Additional Information:10.1007/11618058_13
Classifications:Z Theory > Z.001 General
Z Theory > Z.250 Geometry
ID Code:687

Repository Staff Only: item control page

References

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

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

Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, and Stephen K. Wismath.: Book embeddings and point-set embeddings of series-parallel digraphs. Michael T. Goodrich and Stephen G. Kobourov, eds., Proc. 10th International Symp. on Graph Drawing (GD '02), vol. 2528 of Lecture Notes in Comput. Sci., pp. 162-173. Springer, 2002.

Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, and Dirk Vertigan.: Partitioning graphs of bounded tree-width. Combinatorica, 18(1):1-12, 1998.

Vida Dujmovic and David R. Wood.: On linear layouts of graphs. Discrete Math. Theor. Comput. Sci., 6(2):339-358, 2004.

Vida Dujmovic and David R. Wood.: Graph treewidth and geometric thickness parameters. arXiv.org:math.CO/0503553, 2005.

Joseph L. Ganley and Lenwood S. Heath.: The pagenumber of $k$-trees is O(k). Discrete Appl. Math., 109(3):215-221, 2001.

Richard K. Guy.: Outerthickness and outercoarseness of graphs. Proc. British Combinatorial Conf., vol. 13 of London Math. Soc. Lecture Note Ser., pp. 57-60. Cambridge Univ. Press, 1974.

John H. Halton.: On the thickness of graphs of given degree. Inform. Sci., 54(3):219-238, 1991.

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

Petra Mutzel, Thomas Odenthal, and Mark Scharbrodt.:The thickness of graphs: a survey. Graphs Combin., 14(1):59-73, 1998.

Crispin St. J. A. Nash-Williams.: Decomposition of finite graphs into forests. J. London Math. Soc., 39:12, 1964.

Janos Pach and Rephael Wenger.: Embedding planar graphs at fixed vertex locations. Graphs Combin., 17(4):717-728, 2001.

S. Rengarajan and C. E. Veni Madhavan.: Stack and queue number of 2-trees. Ding-Zhu Du and Ming Li, eds., Proc. 1st Annual International Conf. on Computing and Combinatorics (COCOON '95), vol. 959 of Lecture Notes in Comput. Sci., pp. 203-212. Springer, 1995.

Mihalis Yannakakis.: Embedding planar graphs in four pages. J. Comput. System Sci., 38:36-67, 1986.