Results 41 to 50 of about 98 (93)

2-Layer Graph Drawings with Bounded Pathwidth

Journal of Graph Algorithms and Applications, 2023
This paper determines which properties of 2-layer drawings characterise bipartite graphs of bounded pathwidth.
openaire   +2 more sources

Minor-Closed Graph Classes with Bounded Layered Pathwidth [PDF]

SIAM Journal on Discrete Mathematics, 2020
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 generalises 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.
Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, David R. Wood   +4 more
openaire   +3 more sources

Pathwidth of Circular-Arc Graphs [PDF]

, 2007
The pathwidth of a graph G is the minimum clique number of H minus one, over all interval supergraphs H of G. Although pathwidth is a well-known and well-studied graph parameter, there are extremely few graph classes for which pathwidh is known to be tractable in polynomial time.
Karol Suchan, Ioan Todinca
openaire   +1 more source

Strong-mixed searching and pathwidth [PDF]

Journal of Combinatorial Optimization, 2006
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire   +1 more source

The Behavior of Tree-Width and Path-Width Under Graph Operations and Graph Transformations

Algorithms
Tree-width and path-width are well-known graph parameters. Many NP-hard graph problems admit polynomial-time solutions when restricted to graphs of bounded tree-width or bounded path-width. In this work, we study the behavior of tree-width and path-width
Frank Gurski, Robin Weishaupt
doaj   +1 more source

2-Connecting outerplanar graphs without blowing up the pathwidth [PDF]

Theoretical Computer Science, 2013
Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl, in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on
Babu, Jasine, Basavaraju, Manu, Chandran, L. Sunil, Rajendraprasad, Deepak   +3 more
openaire   +2 more sources

On Exploring Temporal Graphs of Small Pathwidth

arXiv, 2018
We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.
Bodlaender, Hans L., van der Zanden, Tom C.   +1 more
openaire   +5 more sources

On Approximating Cutwidth and Pathwidth

2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
We study graph ordering problems with a min-max objective. A classical problem of this type is cutwidth, where given a graph we want to order its vertices such that the number of edges crossing any point is minimized. We give a $ \log^{1+o(1)}(n)$ approximation for the problem, substantially improving upon the previous poly-logarithmic guarantees based
Bansal, Nikhil, Katzelnick, Dor, Schwartz, Roy   +2 more
openaire   +2 more sources

Editorial. [PDF]

Theor Comput Sci, 2022
Calamoneri T.
europepmc   +1 more source

Selected Papers of the 31st International Workshop on Combinatorial Algorithms, IWOCA 2020. [PDF]

Algorithmica, 2022
Gąsieniec L, Klasing R, Radzik T.
europepmc   +1 more source