Kloks, A.J.J. · Utrecht University Repository (Utrecht University) · 1993
This thesis focuses on problems related to treewidth and pathwidth of graphs. \nMany problems are difficult to solve for graphs in general. The treewidth of a graph is \na good indication whether one can obtain a solution within reasonable time. A \nnecessary ingredient is a treedecomposition of the graph with small width. \nEquivalently, one needs an embedding of the graph into a chordal graph with a \nsmallest possible clique number. \nIn Chapter 2 we start, by giving the definitions. Chapters 3, 4, 5 and 6 deal with \nproblems related to the structure of graphs with bounded treewidth. In Chapter 3 we \nsolve the following problem (stemming from phylogeny). Let G be a graph of which \nthe vertices are colored with 3 colors such that adjacent vertices have a different \ncolor. The problem is to find a chordal embedding of the graph which keeps the \nproperty that adjacent vertices are colored differently. In Chapter 4 we enumerate \nbiconnected partial 2-trees. In Chapter 5, we show that the treewidth of random \ngraphs with a linear number of edges have treewidth which is also linear in the \nnumber of points. This motivates us to look for the treewidth of graphs with a certain \nunderlying structure. We discuss some of these topics in Chapter 7, 8 and 9. \nIn Chapter 6 we show that one can test superperfection for graphs of bounded \ntreewidth in linear time. In Chapter 7 we show that one can approximate, or compute \nexactly, the treewidth of complements of chordal graphs, splitgraphs, convex graphs \nand permutation graphs. For cocomparability graphs we give an algorithm that finds a \npathdecomposition which is quadratic in the treewidth of the graph. Chapter 8 shows \nthat the treewidth of chordal bipartite graphs can be computed in polynomial time. In \nChapter 9 we show a similar result for permutation graphs and we generalize to \ncocomparability graphs of bounded dimension. As a corollary, we show that treewidth \nand pathwidth are the same for cocomparability graphs. In Chapter 9 we deal with the \nproblem of approximating the treewidth of graphs in general. \nIn Chapter 11 and 12 we give algorithms that check whether the pathwidth of a graph \nis at most k. These algorithms can be implemented to run in O(n log n) time.
Cited by 0Open access
Fedor V. Fomin, Dieter Kratsch · Texts in theoretical computer science · 2010
Cited by 3
Kloks, A.J.J. · Data Archiving and Networked Services (DANS) · 1993
This thesis focuses on problems related to treewidth and pathwidth of graphs. \nMany problems are difficult to solve for graphs in general. The treewidth of a graph is \na good indication whether one can obtain a solution within reasonable time. A \nnecessary ingredient is a treedecomposition of the graph with small width. \nEquivalently, one needs an embedding of the graph into a chordal graph with a \nsmallest possible clique number. \nIn Chapter 2 we start, by giving the definitions. Chapters 3, 4, 5 and 6 deal with \nproblems related to the structure of graphs with bounded treewidth. In Chapter 3 we \nsolve the following problem (stemming from phylogeny). Let G be a graph of which \nthe vertices are colored with 3 colors such that adjacent vertices have a different \ncolor. The problem is to find a chordal embedding of the graph which keeps the \nproperty that adjacent vertices are colored differently. In Chapter 4 we enumerate \nbiconnected partial 2-trees. In Chapter 5, we show that the treewidth of random \ngraphs with a linear number of edges have treewidth which is also linear in the \nnumber of points. This motivates us to look for the treewidth of graphs with a certain \nunderlying structure. We discuss some of these topics in Chapter 7, 8 and 9. \nIn Chapter 6 we show that one can test superperfection for graphs of bounded \ntreewidth in linear time. In Chapter 7 we show that one can approximate, or compute \nexactly, the treewidth of complements of chordal graphs, splitgraphs, convex graphs \nand permutation graphs. For cocomparability graphs we give an algorithm that finds a \npathdecomposition which is quadratic in the treewidth of the graph. Chapter 8 shows \nthat the treewidth of chordal bipartite graphs can be computed in polynomial time. In \nChapter 9 we show a similar result for permutation graphs and we generalize to \ncocomparability graphs of bounded dimension. As a corollary, we show that treewidth \nand pathwidth are the same for cocomparability graphs. In Chapter 9 we deal with the \nproblem of approximating the treewidth of graphs in general. \nIn Chapter 11 and 12 we give algorithms that check whether the pathwidth of a graph \nis at most k. These algorithms can be implemented to run in O(n log n) time.
Cited by 0Open access
Hans L. Bodlaender · Lecture notes in computer science · 2005
Cited by 169
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara et al. · 2023
We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most $6 k+5$ under the promise that the treewidth of G never grows above k. The amortized update time is $\mathcal{O}_{k}\left(2^{\sqrt{\log n} \log \log n}\right)$, where n is the vertex count of G and the $\mathcal{O}_{k}(\cdot)$ notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle’s Theorem: for any fixed property $\varphi$ expressible in the CMSO <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> logic, the data structure can maintain whether G satisfies $\varphi$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].
Cited by 2
Hans L. Bodlaender, Joost Engelfriet · 1994
We consider a special variant of tree-decompositions, called domino treedecompositions, and the related notion of domino treewidth. In a domino tree-decomposition, each vertex of the graph belongs to at most two nodes of the tree. We prove that for every k, d, there exists a constant ck;d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most ck;d. The domino treewidth of a tree can be computed in O(n 2 log n) time. There exist polynomial time algorithms that | for fixed k | decide whether a given graph G has domino treewidth at most k. If k is not fixed, this problem is NP-complete. The domino treewidth problem is hard for the complexity classes W [t] for all t 2 N, and hence the problem for fixed k is unlikely to be solvable in O(n c), where c is a constant, not depending on k.
Cited by 0
Bodlaender, H.L. · Utrecht University Repository (Utrecht University) · 1994
Cited by 0Open access
Bodlaender, H.L., Ontwerp en analyse van complexe systemen, Universiteit Utrecht et al. · Data Archiving and Networked Services (DANS) · 1994
We consider a special variant of tree-decompositions, called domino treedecompositions, and the related notion of domino treewidth.In a domino tree-decomposition, each v ertex of the graph belongs to at most two nodes of the tree.We prove that for every k, d, there exists a constant c k;d such that a graph with treewidth at most k and maximum degree at most d has domino treewidth at most c k;d .The domino treewidth of a tree can becomputed in On 2 log n time.There exist polynomial time algorithms that | for xed k | decide whether a given graph G has domino treewidth at most k.If k is not xed, this problem is NP-complete.The domino treewidth problem is hard for the complexity classes W t for all t 2 N, and hence the problem for xed k is unlikely to be solvable in On c , where c is a constant, not depending on k.
Cited by 0Open access
Chiu, Alvin, Depian, Thomas, Eppstein, David et al. · Leibniz-Zentrum für Informatik (Schloss Dagstuhl) · 2025
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.
Cited by 0Open access
Thomas Depian · OSF Preprints (OSF Preprints) · 2025
Cited by 0
Chiu, Alvin, Depian, Thomas, Eppstein, David et al. · ArXiv.org · 2025
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with ''tracks'' for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.
Cited by 0Open access
Hans L. Bodlaender · 2006
Cited by 0
Hans L. Bodlaender, Joost Engelfriet · 1994
Cited by 0
L. Sunil Chandran, Naveen Sivadasan · Journal of Combinatorial Theory Series B · 2007
Cited by 73
Vincent Bouchitté, Dieter Kratsch, Haiko Miiller et al. · Electronic Notes in Discrete Mathematics · 2001
Cited by 10
Arie M. C. A. Koster, Hans L. Bodlaender, C.P.M. van Hoesel · Data Archiving and Networked Services (DANS) · 2002
Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed $k$, linear time algorithms exist to solve the decision problem ``treewidth $\leq k$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.
Cited by 11Open access
Hans L. Bodlaender · Encyclopedia of Algorithms · 2014
Cited by 6
Zdenĕk Dvořák · Springer monographs in mathematics · 2025
Cited by 0
David Eppstein · Notices of the American Mathematical Society · 2025
The treewidth of a graph, a positive integer defined using a tree of sets of vertices, is central to graph structure theory and the parametrized complexity of algorithms.Its many areas of application include sparse numerical linear algebra, Bayesian inference, control theory, game theory, lowdimensional topology, network science, and algebraic geometry. DefinitionsA common definition of treewidth involves treedecompositions, of which the following is a special case.A graph is outerplanar if it can be drawn with its vertices on the boundary of a disk and its edges as noncrossing curves in the disk.Adding artificial edges, we can augment this drawing to a triangulation, a subdivision of the disk into triangles (Fig. 1), with the following properties:
Cited by 1Open access
Chandra Chekuri · Open Collections · 2015
Cited by 0Open access