Orthogonal Tree Decompositions of Graphs
From MaRDI portal
Publication:4634649
DOI10.1137/17M1112637zbMath1383.05257arXiv1701.05639MaRDI QIDQ4634649
Vida Dujmović, Pat Morin, Gwenaël Joret, 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
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Corrigendum: Orthogonal Tree Decompositions of Graphs, Track layouts, layered path decompositions, and leveled planarity, Burling graphs, chromatic number, and orthogonal tree-decompositions, Burling graphs, chromatic number, and orthogonal tree-decompositions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- Tree-chromatic number
- Separator theorems and Turán-type results for planar intersection graphs
- On tree-partition-width
- Graph minors. I. Excluding a forest
- Interval representations of planar graphs
- String graphs. II: Recognizing string graphs is NP-hard
- Helly families of maximal size
- A partial k-arboretum of graphs with bounded treewidth
- Graph minors. XVI: Excluding a non-planar graph
- Diameter and treewidth in minor-closed graph families
- Track layouts, layered path decompositions, and leveled planarity
- Excluding any graph as a minor allows a low tree-width 2-coloring
- Recognizing string graphs is decidable
- Decidability of string graphs
- Applications of the crossing number
- Complete graph minors and the graph minor structure theorem
- The graph crossing number and its variants: a survey
- Treewidth of graphs with balanced separations
- Separating tree-chromatic number from path-chromatic number
- Layered separators in minor-closed graph classes with applications
- Local tree-width, excluded minors, and approximation algorithms
- On tree width, bramble size, and expansion
- Boxicity and treewidth
- Approximation Algorithms for Independent Sets in Map Graphs
- Strongly Sublinear Separators and Polynomial Expansion
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Stack and Queue Layouts via Layered Separators
- Parameters Tied to Treewidth
- A Separator Theorem for String Graphs and its Applications
- New tools and results in graph minor structure theory
- String graphs and separators
- Map graphs
- On a Coloring Problem.
- New bounds on the edge number of ak-map graph
- Graph minors. II. Algorithmic aspects of tree-width
- A Separator Theorem for Nonplanar Graphs
- On VLSI layouts of the star graph and related networks
- Domino Treewidth
- Separators in region intersection graphs
- Crossing Numbers and Cutwidths
- On the chordality of a graph
- Bidimensional Parameters and Local Treewidth
- Structure of Graphs with Locally Restricted Crossings
- Tree‐Chromatic Number Is Not Equal to Path‐Chromatic Number*
- Applications of a New Separator Theorem for String Graphs
- Near-Optimal Separators in String Graphs
- Parameterized Algorithms
- Recognizing string graphs in NP
- Burling graphs, chromatic number, and orthogonal tree-decompositions
