Reducing a given street network to a public transport network is essential for bundling passenger demand and reducing the environmental impact of mobility. Here, both the operators’ budget and the passengers’ routing costs have to be considered. We introduce a new integer programming model for designing routing-cost-minimal public transport networks in circular cities leveraging their symmetry. In an extensive computational study, we compare generic and symmetric sub-networks structurally, show that the newly introduced model can be solved orders of magnitude faster than generic models and determine that the routing-cost gap between symmetric and generic sub-networks can be disregarded for most budgets.

Twin-width is a graph parameter introduced in the context of first-order model checking, and has since become a central parameter in algorithmic graph theory. While many algorithmic problems become easier on arbitrary classes of bounded twin-width, graph isomorphism on graphs of twin-width 4 and above is as hard as the general isomorphism problem. For each positive integer k, the k-dimensional Weisfeiler-Leman algorithm is an iterative color refinement algorithm that encodes structural similarities and serves as a fundamental tool for distinguishing non-isomorphic graphs. We show that the graph isomorphism problem for graphs of twin-width 1 can be solved by the 3-dimensional Weisfeiler-Leman algorithm, while there is no fixed k such that the k-dimensional Weisfeiler-Leman algorithm solves the graph isomorphism problem for graphs of twin-width 4. Moreover, we prove the conjecture of Bergougnoux, Gajarský, Guspiel, Hlinený, Pokrývka, and Sokolowski (ISAAC 2023) that stable graphs of twin-width 2 have bounded rank-width. This implies that isomorphism of these graphs is solved by a fixed dimension of the Weisfeiler-Leman algorithm.

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g ≥ 1 and recovers the known tight bound for the planar case ( g = 0 ).

The twin-width of a graph measures its distance to co-graphs and generalizes classical width concepts such as tree-width or rank-width. Since its introduction in 2020 (Bonnet et al., 2022), a mass of new results has appeared relating twin-width to group theory, model theory, combinatorial optimization, and structural graph theory. We take a detailed look at the interplay between the twin-width of a graph and the twin-width of its components under tree-structured decompositions: We prove that the twin-width of a graph of strong tree-width k is at most 3 2 k + o ( k ) , contrasting nicely with the result of Bonnet and Déprés (2023), which states that twin-width can be exponential in tree-width. Further, we employ the fundamental concept from structural graph theory of decomposing a graph into highly connected components, in order to obtain optimal linear bounds on the twin-width of a graph given the widths of its biconnected components. For triconnected components we obtain a linear upper bound if we add red edges to the components indicating the splits which led to the components. Extending this approach to quasi-4-connectivity, we obtain a quadratic upper bound. Finally, we investigate how the adhesion of a tree decomposition influences the twin-width of the decomposed graph.

Abstract. A colored graph is [Formula: see text]-ultrahomogeneous if every isomorphism between two induced subgraphs of order at most [Formula: see text] extends to an automorphism. A colored graph is [Formula: see text]-tuple regular if the number of vertices adjacent to every vertex in a set [Formula: see text] of order at most [Formula: see text] depends only on the isomorphism type of the subgraph induced by [Formula: see text]. We classify the finite vertex-colored [Formula: see text]-ultrahomogeneous graphs and the finite vertex-colored [Formula: see text]-tuple regular graphs for [Formula: see text] and [Formula: see text], respectively. Our theorem in particular classifies finite vertex-colored ultrahomogeneous graphs, where ultrahomogeneous means the graph is simultaneously [Formula: see text]-ultrahomogeneous for all [Formula: see text].

Line planning, i.e. choosing routes which are to be serviced by vehicles in order to satisfy network demands, is an important aspect of public transport planning. While there exist heuristic procedures for generating lines from scratch, most theoretical investigations consider the problem of choosing lines only from a predefined line pool. We consider the line planning problem when all simple paths can be used as lines and present an algorithm which is fixed-parameter tractable, i.e. it is efficient on instances with small parameter. As a parameter we consider the treewidth of the public transport network, along with its maximum degree as well as the maximum allowed frequency.

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g>0 and recovers the known tight bound for the planar case (g=0).

The twin-width of a graph measures its distance to co-graphs and generalizes classical width concepts such as tree-width or rank-width. Since its introduction in 2020 (Bonnet et. al. 2020), a mass of new results has appeared relating twin width to group theory, model theory, combinatorial optimization, and structural graph theory. We take a detailed look at the interplay between the twin-width of a graph and the twin-width of its components under tree-structured decompositions: We prove that the twin-width of a graph is at most twice its strong tree-width, contrasting nicely with the result of (Bonnet and Déprés 2022), which states that twin-width can be exponential in tree-width. Further, we employ the fundamental concept from structural graph theory of decomposing a graph into highly connected components, in order to obtain an optimal linear bound on the twin-width of a graph given the widths of its biconnected components. For triconnected components we obtain a linear upper bound if we add red edges to the components indicating the splits which led to the components. Extending this approach to quasi-4-connectivity, we obtain a quadratic upper bound. Finally, we investigate how the adhesion of a tree decomposition influences the twin-width of the decomposed graph.

The 3-decomposition conjecture is wide open. It asserts that every finite connected cubic graph can be decomposed into a spanning tree, a disjoint union of cycles, and a matching. We prove that the following graphs are reducible configurations for the 3-decomposition conjecture: the triangle, the K2,3, the claw-square, the twin-house, and the domino. As an application, we show that all 3-connected cubic graphs of path-width at most 4 satisfy the 3-decomposition conjecture.