A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. We prove that, in the class of connected hypergraphs without bridges and loops that ...

It is not difficult to think of applications that can be modelled as graph problems in which placing some facility or commodity at a vertex has some positive or negative effect on the values of all the vertices out to some distance, and we want to ...

A k-page upward book embedding (kUBE) of a directed acyclic graph G is a book embeddings of G on k pages with the additional requirement that the vertices appear in a topological ordering along the spine of the book. The kUBE Testing problem, ...$\mathrm{}$$\mathrm{}$$\mathrm{}$${}^{\mathrm{}}$$$$$$\mathrm{}$

Public transportation networks are typically operated with a periodic timetable. The periodic event scheduling problem (PESP) is the standard mathematical modeling tool for periodic timetabling. PESP is a computationally very challenging problem: ...

Branch decomposition is a prominent method for structurally decomposing a graph, a hypergraph, or a propositional formula in conjunctive normal form. The width of a branch decomposition provides a measure of how well the object is decomposed. For many ...

Many algorithms have been developed for NP-hard problems on graphs with small treewidth k. For example, all problems that are expressible in linear extended monadic second order can be solved in linear time on graphs of bounded treewidth. It turns out ...

A k -outerplanar graph is a graph that can be drawn in the plane without crossing such that after k -fold removal of the vertices on the outer-face there are no vertices left. In this paper, we study how to triangulate a k -outerplanar graph while ...

For graph G, let źbw(G) denote the branchwidth of G and źgm(G) the largest integer g such that G contains a g g grid as a minor. We show that źbw(G)≤3źgm(G) for every planar graph G. This is an improvement over the bound źbw(G)≤4źgm(G) due to Robertson, ...

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is ...

In this paper, we consider the problem of computing an optimal branch decomposition of a graph. Branch decompositions and branchwidth were introduced by Robertson and Seymour in their series of papers that proved the Graph Minors Theorem. Branch ...

The H-Minor containment problem asks whether a graph G contains some fixed graph H as a minor, that is, whether H can be obtained by some subgraph of G after contracting edges. The derivation of a polynomial-time algorithm for H-Minor containment is one ...

A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. Self-duality has been examined for several width parameters, such as branchwidth, pathwidth, ...

The Planar Feedback Vertex Set problem asks whether an n-vertex planar graph contains at most k vertices meeting all its cycles. The Face Cover problem asks whether all vertices of a plane graph G lie on the boundary of at most k faces of G. Standard ...

We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined ...

This article presents an infinite family of combinatorial problems that shows abrupt changes of complexity between neighbour problems. We define problem P"k^l as a purely constraint-driven variant of hypergraph partitioning with parameters k and l as ...

Minimal triangulations and potential maximal cliques are the main ingredients for a number of polynomial time algorithms on different graph classes computing the treewidth of a graph. Potential maximal cliques are also the main engine of the fastest so ...

Treewidth and branchwidth are two closely related connectivity parameters of graphs. Graphs of treewidth at most k have well-known alternative characterizations as subgraphs of chordal graphs and as partial k-trees. In this paper we give analogous ...