Orthogonal tree decompositions of graphs

Vida Dujmovic, Gwenaël Joret, Pat Morin, Sergey Norin, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

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(n) 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.

Original languageEnglish
Pages (from-to)839-863
Number of pages25
JournalSIAM Journal on Discrete Mathematics
Volume32
Issue number2
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Layered treewidth
  • Orthogonal tree decomposition
  • Tree decomposition
  • Treewidth

Cite this

Dujmovic, Vida ; Joret, Gwenaël ; Morin, Pat ; Norin, Sergey ; Wood, David R. / Orthogonal tree decompositions of graphs. In: SIAM Journal on Discrete Mathematics. 2018 ; Vol. 32, No. 2. pp. 839-863.
@article{e38e4a6a6bd149b9b697f2e30eccc3e9,
title = "Orthogonal tree decompositions of graphs∗",
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(n) 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.",
keywords = "Layered treewidth, Orthogonal tree decomposition, Tree decomposition, Treewidth",
author = "Vida Dujmovic and Gwena{\"e}l Joret and Pat Morin and Sergey Norin and Wood, {David R.}",
year = "2018",
month = "1",
day = "1",
doi = "10.1137/17M1112637",
language = "English",
volume = "32",
pages = "839--863",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics",
number = "2",

}

Dujmovic, V, Joret, G, Morin, P, Norin, S & Wood, DR 2018, 'Orthogonal tree decompositions of graphs', SIAM Journal on Discrete Mathematics, vol. 32, no. 2, pp. 839-863. https://doi.org/10.1137/17M1112637

Orthogonal tree decompositions of graphs. / Dujmovic, Vida; Joret, Gwenaël; Morin, Pat; Norin, Sergey; Wood, David R.

In: SIAM Journal on Discrete Mathematics, Vol. 32, No. 2, 01.01.2018, p. 839-863.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Orthogonal tree decompositions of graphs∗

AU - Dujmovic, Vida

AU - Joret, Gwenaël

AU - Morin, Pat

AU - Norin, Sergey

AU - Wood, David R.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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(n) 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.

AB - 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(n) 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.

KW - Layered treewidth

KW - Orthogonal tree decomposition

KW - Tree decomposition

KW - Treewidth

UR - http://www.scopus.com/inward/record.url?scp=85049580961&partnerID=8YFLogxK

U2 - 10.1137/17M1112637

DO - 10.1137/17M1112637

M3 - Article

AN - SCOPUS:85049580961

VL - 32

SP - 839

EP - 863

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -