67 citations · 377 across the 34 of their papers we have counts for
3 papers · 1 filter
Separator Theorem and Algorithms for Planar Hyperbolic Graphs
Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen +2
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incompa…
Cliquewidth and dimension
Gwenaël Joret, Piotr Micek, Michał Pilipczuk +1
We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension as a subposet. This applies in particular to…
Tight bound on treedepth in terms of pathwidth and longest path
Meike Hatzel, Gwenaël Joret, Piotr Micek +3
We show that every graph with pathwidth strictly less than that contains no path on vertices as a subgraph has treedepth at most . The bound is best possible up to…