Search

The circumference of a graph G with at least one cycle is the length of a longest cycle in G. A classic result of Birmel\'e [J. Graph Theory, 43 (2003), pp. 24--25] states that the treewidth of G is at most its circumference minus 1. In case G is 2-connected, this upper bound also holds for the pathwidth of G; in fact, even the treedepth of G is upper bounded by its circumference (Bria\'nski et al. [Treedepth vs circumference, Combinatorica, 43 (2023), pp. 659--664]). In this paper, we study whether similar bounds hold when replacing the circumference of G by its cocircumference, defined as the largest size of a bond in G, an inclusionwise minimal set of edges F such that G F has more components than G. In matroidal terms, the cocircumference of G is the circumference of the bond matroid of G. Our first result is the following "dual" version of Birmel'e's theorem: The treewidth of a graph G is at most its cocircumference. Our second and main result is an upper bound of 3k 2 on the pathwidth of a 2-connected graph G with cocircumference k. Contrary to circumference, no such bound holds for the treedepth of G. Our two upper bounds are best possible up to a constant factor. [ABSTRACT FROM AUTHOR]

Given two n-vertex graphs G1 and G2 of bounded treewidth, is there an n-vertex graph G of bounded treewidth having subgraphs isomorphic to G1 and G2? Our main result is a negative answer to this question, in a strong sense: we show that the answer is no even if G1 is a binary tree and G2 is a ternary tree. We also provide an extensive study of cases where such "gluing"" is possible. In particular, we prove that if G1 has treewidth k and G2 has pathwidth \l, then there is an n-vertex graph of treewidth at most k + 3\l + 1 containing both G1 and G2 as subgraphs. [ABSTRACT FROM AUTHOR]

We study the problem of embedding shortest-path metrics of weighted graphs into ℓp spaces. We introduce a new embedding technique based on low-depth decompositions of a graph via shortest paths. The notion of shortest path decomposition (SPD) depth is inductively defined: A (weighed) path graph has SPD depth 1. General graph has an SPD of depth k if it contains a shortest path whose deletion leads to a graph, each of whose components has SPD depth at most k - 1. In this paper we give an O(kmin{1/p,1/2})-distortion embedding for graphs of SPD depth at most k. This result is asymptotically tight for any fixed p > 1, while for p = 1 it is tight up to second order terms. As a corollary of this result, we show that graphs having pathwidth k embed into ℓp with distortion O(kmin{1/p,1/2}). For p = 1, this improves over the best previous bound of Lee and Sidiropoulos that was exponential in k; moreover, for other values of p it gives the first embeddings whose distortion is independent of the graph size n. Furthermore, we use the fact that planar graphs have SPD depth O(log n) to give a new proof that any planar graph embeds into ℓ1 with distortion O(√ log n). Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor. [ABSTRACT FROM AUTHOR]

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalizes a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class. [ABSTRACT FROM AUTHOR]

We give asymptotically exact values for the treewidth tw(G) of a random geometric graph G ∈ G(n, r) in [0, √n]². More precisely, let rc denote the threshold radius for the appearance of the giant component in G(n, r). We then show that for any constant 0 < r < rc, tw(G) = Θ(log n/log log n), and for c being sufficiently large, and r = r(n) ≥ c, tw(G) = Θ(r√n). Our proofs show that for the corresponding values of r the same asymptotic bounds also hold for the pathwidth and the treedepth of a random geometric graph. [ABSTRACT FROM AUTHOR]

We consider relations between the size, treewidth, and local crossing number (maximum number of crossings per edge) of graphs embedded on topological surfaces. We show that an n-vertex graph embedded on a surface of genus g with at most k crossings per edge has treewidth O(√(g + 1)(k + 1)n) and layered treewidth O((g + 1)k) and t hat these bounds are tight up to a constant factor. In the special case of g = 0, so-called k-planar graphs, the treewidth bound is O(√((k + 1)n), which is tight and improves upon a known O( (k + 1)3/4n1/2) bound. Analogous results are proved for map graphs defined with respect to any surface. Finally, we show that for g < m, every m-edge graph can be embedded on a surface of genus g with O((m/(g + 1)) log² g) crossings per edge, which is tight to a polylogarithmic factor. [ABSTRACT FROM AUTHOR]

In the mixed Chinese postman problem (MCPP), given a weighted mixed graph G (it may have both edges and arcs), our aim is to find a closed walk of minimum weight traversing each edge and arc at least once. The MCPP parameterized by the number of edges in G or the number of arcs in G is fixed-parameter tractable as proved by van Bevern et al. in 2014 and Gutin, Jones, and Sheng in 2014, respectively. Solving an open question of van Bevern et al., we show that somewhat unexpectedly the MCPP parameterized by the (undirected) treewidth of G is W[1]-hard. In fact, we prove that even the unweighted MCPP parameterized by the pathwidth of G is W[1]-hard. On the positive side, we show that MCPP parameterized by treedepth is fixed-parameter tractable (even with arbitrary integer weights). We are unaware of any widely studied graph parameters between pathwidth and treedepth and so our results provide a close characterization of the complexity of MCPP. [ABSTRACT FROM AUTHOR]

It is proven that the connected pathwidth of any graph G is at most 2 · pw(G)+1, where pw(G) is the pathwidth of G. The method is constructive, i.e., it yields an efficient algorithm that for a given path decomposition of width k computes a connected path decomposition of width at most 2k+1. The running time of the algorithm is O(dk²), where d is the number of "bags" in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality cs(G) ≤ 2s(G) + 3, where cs(G) and s(G) are the connected search number and the search number of G, respectively. Moreover, the algorithm presented in this work can be used to convert a given search strategy using k searchers into a (monotone) connected one using 2k + 3 searchers and starting at an arbitrary homebase. [ABSTRACT FROM AUTHOR]

Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in monadic second-order logic with second-order quantification on vertex sets, which includes NP-hard problems such as 3-colorability) can be solved in polynomial time for graphs of bounded clique-width. We show that the clique-width of a given graph cannot be absolutely approximated in polynomial time unless P = NP. We also show that, given a graph G and an integer k, deciding whether the clique-width of G is at most k is NP-complete. This solves a problem that has been open since the introduction of clique-width in the early 1990s. [ABSTRACT FROM AUTHOR]

We define helicopter cops and robber games with multiple robbers, extending previous research, which considered only the pursuit of a single robber. Our model is defined for robbers that are visible (their position in the graph is known to the cops) and active (they can move at any point in the game) but is easily adapted to other variants of the single-robber game that have been considered in the literature. We show that the game with many robbers is nonmonotone: that is, fewer cops are needed if the robbers are allowed to reoccupy positions that were previously unavailable to them. As the moves of the cops depend on the position of the visible robbers, strategies for such games should be interactive, but the game becomes, in a sense, less interactive as the initial number of robbers increases. We prove that the main parameter emerging from the game, which we denote mvams(G, r), captures a hierarchy of parameters between proper pathwidth and proper treewidth, and we completely characterize it for trees, extending analogous existing characterizations of the pathwidth of trees. Moreover, we prove an upper bound for mvams(G, r) on general graphs and show that this bound is reached by an infinite class of graphs. On the other hand, if we consider the robbers to be invisible and lazy, the resulting parameters collapse in all cases to either proper pathwidth or proper treewidth, giving a further case where the classical equivalence between visible, active robbers and invisible, lazy robbers does not hold. [ABSTRACT FROM AUTHOR]