Results 31 to 40 of about 1,027 (141)
Approximation of pathwidth of outerplanar graphs [PDF]
Journal of Algorithms, 2001 Summary: There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph \(G\), finds a path decomposition of \(G\) of pathwidth at most twice the pathwidth of \(G\) plus one.
Hans L. Bodlaender, Fedor V. Fomin
openaire +6 more sources
Grundy Distinguishes Treewidth from Pathwidth
SIAM Journal on Discrete Mathematics, 2022 Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to understand the "price of generality" of these widths: as we transition from more restrictive to more general notions, which are the problems that see their complexity status ...
Rémy Belmonte +4 more
openaire +4 more sources
Linear Datalog and Bounded Path Duality of Relational Structures [PDF]
Logical Methods in Computer Science, 2005 In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs.
Victor Dalmau
doaj +1 more source
On the treewidth of triangulated 3-manifolds
Journal of Computational Geometry, 2019 In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how "simple" or "thin" a given graph or 3-manifold is.
Kristóf Huszár +2 more
doaj +1 more source
The Pebble-Relation Comonad in Finite Model Theory [PDF]
Logical Methods in Computer ScienceThe pebbling comonad, introduced by Abramsky, Dawar and Wang, provides a categorical interpretation for the k-pebble games from finite model theory.
Yoàv Montacute, Nihil Shah
doaj +1 more source
Pathwidth and Nonrepetitive List Coloring
The Electronic Journal of Combinatorics, 2016 A vertex coloring of a graph is nonrepetitive if there is no path in the graph whose first half receives the same sequence of colors as the second half. While every tree can be nonrepetitively colored with a bounded number of colors (4 colors is enough), Fiorenzi, Ochem, Ossona de Mendez, and Zhu recently showed that this does not extend to the list ...
Gagol, Adam +3 more
openaire +6 more sources
The Bounded Pathwidth of Control-Flow Graphs
, 2023 Pathwidth and treewidth are standard and well-studied graph sparsity parameters which intuitively model the degree to which a given graph resembles a path or a tree, respectively.
Goharshady, Amir Kafshdar +2 more
core +1 more source
On the Complexity of Embedding in Graph Products
Computing in Geometry and TopologyGraph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph G in a host graph that is the strong product of a path ...
Therese Biedl +2 more
doaj +1 more source
Order-preserving Drawings of Trees with Approximately Optimal Height (and Small Width)
Journal of Graph Algorithms and Applications, 2020 In this paper, we study how to draw trees so that they are planar, straight-line and respect a given order of edges around each node. We focus on minimizing the height, and show that we can always achieve a height of at most $2pw(T)+1$, where $pw(T ...
Johannes Batzill, Therese Biedl
doaj +1 more source
Parameterized Complexity of 1-Planarity
Journal of Graph Algorithms and Applications, 2018 We consider the problem of drawing graphs with at most one crossing per edge. These drawings, and the graphs that can be drawn in this way, are called $1$-planar.
Michael Bannister +2 more
doaj +1 more source