×

The treewidth of line graphs. (English) Zbl 1391.05218

Summary: The treewidth of a graph is an important invariant in structural and algorithmic graph theory. This paper studies the treewidth of line graphs. We show that determining the treewidth of the line graph of a graph \(G\) is equivalent to determining the minimum vertex congestion of an embedding of \(G\) into a tree. Using this result, we prove sharp lower bounds in terms of both the minimum degree and average degree of \(G\). These results are precise enough to exactly determine the treewidth of the line graph of a complete graph and other interesting examples. We also improve the best known upper bound on the treewidth of a line graph. Analogous results are proved for pathwidth.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C38 Paths and cycles
05C12 Distance in graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Atserias, A., On digraph coloring problems and treewidth duality, European J. Combin., 29, 4, 796-820, (2008) · Zbl 1160.05024
[2] Bhatt, S. N.; Leighton, F. T., A framework for solving VLSI graph layout problems, J. Comput. System Sci., 28, 2, 300-343, (1984) · Zbl 0543.68052
[3] Bienstock, D., On embedding graphs in trees, J. Combin. Theory Ser. B, 49, 1, 103-136, (1990) · Zbl 0646.05025
[4] Bodlaender, H. L., A tourist guide through treewidth, Acta Cybernet., 11, 1-2, 1-21, (1993) · Zbl 0804.68101
[5] Bodlaender, H. L.; Fellows, M. R.; Hallett, M. T.; Wareham, H. T.; Warnow, T. J., The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Theoret. Comput. Sci., 244, 1-2, 167-188, (2000) · Zbl 0945.68145
[6] Bodlaender, H. L.; Fellows, M. R.; Thilikos, D. M., Derivation of algorithms for cutwidth and related graph layout parameters, J. Comput. System Sci., 75, 4, 231-244, (2009) · Zbl 1165.68523
[7] Călinescu, G.; Fernandes, C. G.; Reed, B., Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width, J. Algorithms, 48, 2, 333-359, (2003) · Zbl 1079.68069
[8] Chung, F. R.K., On the cutwidth and the topological bandwidth of a tree, SIAM J. Algebr. Discrete Methods, 6, 2, 268-277, (1985) · Zbl 0565.05019
[9] DeVos, M.; Dvořák, Z.; Fox, J.; McDonald, J.; Mohar, B.; Scheide, D., A minimum degree condition forcing complete graph immersion, Combinatorica, 34, 3, 279-298, (2014) · Zbl 1349.05180
[10] Gavril, F., Some NP-complete problems on graphs, (Proceedings of the 11th Conference on Information Sciences and Systems, (1977), Johns Hopkins University Baltimore, MD), 91-95
[11] Golovach, P. A., The cut width of a graph and the vertex separation number of the line graph, Discrete Math. Appl., 3, 5, 517-521, (1993) · Zbl 0799.05035
[12] Grohe, M.; Marx, D., On tree width, bramble size, and expansion, J. Combin. Theory Ser. B, 99, 1, 218-228, (2009) · Zbl 1205.05049
[13] Harvey, D. J., On treewidth and graph minors, (2014), The University of Melbourne, PhD thesis
[14] Harvey, D. J.; Wood, D. R., Treewidth of the line graph of a complete graph, J. Graph Theory, 79, 1, 48-54, (2015) · Zbl 1312.05116
[15] Harvey, D. J.; Wood, D. R., Parameters tied to treewidth, J. Graph Theory, 84, 4, 364-385, (2017) · Zbl 1359.05030
[16] Kinnersley, N. G., The vertex separation number of a graph equals its path-width, Inform. Process. Lett., 42, 6, 345-350, (1992) · Zbl 0764.68121
[17] Korach, E.; Solel, N., Tree-width, path-width, and cutwidth, Discrete Appl. Math., 43, 1, 97-101, (1993) · Zbl 0788.05057
[18] Lengauer, T., Black-white pebbles and graph separation, Acta Inform., 16, 4, 465-475, (1981) · Zbl 0454.68027
[19] Lucena, B., Achievable sets, brambles, and sparse treewidth obstructions, Discrete Appl. Math., 155, 8, 1055-1065, (2007) · Zbl 1116.05076
[20] Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H., Topological bandwidth, SIAM J. Algebr. Discrete Methods, 6, 3, 418-444, (1985) · Zbl 0573.05052
[21] Marx, D., Can you beat treewidth?, Theory Comput., 6, 5, 85-112, (2010) · Zbl 1213.68316
[22] Matsubayashi, A.; Ueno, S., Small congestion embedding of graphs into hypercubes, Networks, 33, 1, 71-77, (1999) · Zbl 0990.05036
[23] Robertson, N.; Seymour, P. D., Graph minors I-XXIII, J. Combin. Theory Ser. B, (1983-2012)
[24] Robertson, N.; Seymour, P. D., Graph minors. II. algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322, (1986) · Zbl 0611.05017
[25] M. Saks, Personal communication to D. Bienstock, reported in [3]; M. Saks, Personal communication to D. Bienstock, reported in [3]
[26] Thilikos, D. M.; Serna, M.; Bodlaender, H. L., Cutwidth. I. A linear time fixed parameter algorithm, J. Algorithms, 56, 1, 1-24, (2005) · Zbl 1161.68856
[27] Thilikos, D. M.; Serna, M.; Bodlaender, H. L., Cutwidth. II. algorithms for partial w-trees of bounded degree, J. Algorithms, 56, 1, 25-49, (2005) · Zbl 1161.68857
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.