Orthogonal tree decompositions of graphs

DOI10.1137/17M1112637MaRDI QIDQ4634649zbMATH OpenFDO

Authors Vida Dujmović, Gwenaël Joret, Pat Morin, David R. Wood, Serguei Norine

Publication date 11 April 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05639

zbMATH Keywords

layered treewidthorthogonal tree decompositiontree decompositiontreewidth

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the second decomposition. We show that every graph in each of the following classes has a tree decomposition and a linear-sized path decomposition with bounded intersections: (1) every proper minor-closed class, (2) string graphs with a linear number of crossings in a fixed surface, (3) graphs with linear crossing number in a fixed surface. Here `linear size' means that the total size of the bags in the path decomposition is $O(n)$ for $n$-vertex graphs. We then show that every $n$-vertex graph that has a tree decomposition and a linear-sized path decomposition with bounded intersections has $O(sqrtn)$ treewidth. As a corollary, we conclude a new lower bound on the crossing number of a graph in terms of its treewidth. Finally, we consider graph classes that have two path decompositions with bounded intersections. Trees and outerplanar graphs have this property. But for the next most simple class, series parallel graphs, we show that no such result holds.

Recommendations

• Planar Decompositions and the Crossing Number of Graphs with an Excluded Minor
• Planar decompositions and the crossing number of graphs with an excluded minor
• scientific article; zbMATH DE number 7278018
• scientific article; zbMATH DE number 4210186
• Structure of graphs with locally restricted crossings

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• A Separator Theorem for Nonplanar Graphs
• A separator theorem for string graphs and its applications
• Applications of a new separator theorem for string graphs
• Applications of the crossing number
• Approximation algorithms for independent sets in map graphs
• Bidimensional Parameters and Local Treewidth
• Boxicity and treewidth
• Burling graphs, chromatic number, and orthogonal tree-decompositions
• Complete graph minors and the graph minor structure theorem
• Crossing Numbers and Cutwidths
• Decidability of string graphs
• Diameter and treewidth in minor-closed graph families
• Domino Treewidth
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Excluding any graph as a minor allows a low tree-width 2-coloring
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XVI: Excluding a non-planar graph
• Helly families of maximal size
• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 1375581 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 7053376 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• Interval representations of planar graphs
• Layered separators in minor-closed graph classes with applications
• Local tree-width, excluded minors, and approximation algorithms
• Map graphs
• Near-optimal separators in string graphs
• New bounds on the edge number of ak-map graph
• New tools and results in graph minor structure theory
• On a Coloring Problem.
• On the chordality of a graph
• On tree width, bramble size, and expansion
• On tree-partition-width
• On VLSI layouts of the star graph and related networks
• Parameterized algorithms
• Parameters tied to treewidth
• Recognizing string graphs in NP
• Recognizing string graphs is decidable
• Separating tree-chromatic number from path-chromatic number
• Separator theorems and Turán-type results for planar intersection graphs
• Separators in region intersection graphs
• Sparsity. Graphs, structures, and algorithms
• String graphs and separators
• String graphs. II: Recognizing string graphs is NP-hard
• Strongly sublinear separators and polynomial expansion
• Structure of graphs with locally restricted crossings
• The graph crossing number and its variants: a survey
• Track layouts, layered path decompositions, and leveled planarity
• Tree-chromatic number
• Tree-chromatic number is not equal to path-chromatic number
• Treewidth of graphs with balanced separations

Cited in

(10)

• Track layouts, layered path decompositions, and leveled planarity
• Decomposition into two trees with orientation constraints
• Planar decompositions and the crossing number of graphs with an excluded minor
• Corrigendum: Orthogonal Tree Decompositions of Graphs
• Burling graphs, chromatic number, and orthogonal tree-decompositions
• Burling graphs, chromatic number, and orthogonal tree-decompositions
• Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Graphs of bounded chordality
• Assouad-Nagata dimension of minor-closed metrics

This page was built for publication: Orthogonal tree decompositions of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4634649)