HOPS web view

This page contains lists for:


Parameters

Simplified Hasse hierarchy (source)

Hasse hierarchy (source)

Simplified comparison table (pdf, full-pdf)

This browser does not support PDFs. Please download the PDF to view it: Download PDF.


All parameters in HOPS

Parameter*Relevance
acyclic chromatic number█████░░░░
admissibility█████░░░░
arboricity█████░░░░
average degree██░░░░░░░
average distance███░░░░░░
bandwidth█████░░░░
bipartite number██░░░░░░░
bisection bandwidth████░░░░░
book thickness████░░░░░
boolean width█████░░░░
bounded components███░░░░░░
boxicity██████░░░
branch width████░░░░░
c-closure░░░░░░░░░
carving-width███░░░░░░
chordality████░░░░░
chromatic number█████░░░░
clique cover number█████░░░░
clique-tree-width██░░░░░░░
clique-width███████░░
contraction complexity██░░░░░░░
cutwidth████░░░░░
d-admissibility████░░░░░
d-path-free██░░░░░░░
degeneracy██████░░░
degree treewidth██████░░░
diameter██████░░░
diameter+max degree░░░░░░░░░
distance to bipartite█████░░░░
distance to block████░░░░░
distance to bounded components████░░░░░
distance to chordal████░░░░░
distance to cluster█████░░░░
distance to co-cluster█████░░░░
distance to cograph█████░░░░
distance to complete██████░░░
distance to edgeless█░░░░░░░░
distance to forest█████░░░░
distance to interval███░░░░░░
distance to linear forest████░░░░░
distance to maximum degree████░░░░░
distance to outerplanar███░░░░░░
distance to perfect████░░░░░
distance to planar████░░░░░
distance to stars███░░░░░░
domatic number███░░░░░░
domination number███░░░░░░
domino treewidth███░░░░░░
edge clique cover number████░░░░░
edge connectivity██░░░░░░░
edge-cut width██░░░░░░░
edge-treewidth██░░░░░░░
feedback edge set██████░░░
feedback vertex set████████░
flip-width█████░░░░
genus██████░░░
h-index████░░░░░
iterated type partitions███░░░░░░
linear clique-width████░░░░░
linear NLC-width██░░░░░░░
linear rank-width██░░░░░░░
maximum clique█████░░░░
maximum degree████████░
maximum independent set██░░░░░░░
maximum induced matching███░░░░░░
maximum leaf number██████░░░
maximum matching███░░░░░░
maximum matching on bipartite graphs░░░░░░░░░
merge-width█████░░░░
mim-width██████░░░
minimum degree░░░░░░░░░
mm-width████░░░░░
modular-width███████░░
module-width████░░░░░
neighborhood diversity██████░░░
NLC-width████░░░░░
NLCT-width██░░░░░░░
odd cycle transversal██████░░░
overlap treewidth██░░░░░░░
pathwidth████████░
pathwidth+maxdegree███░░░░░░
radius-inf flip-width███░░░░░░
radius-r flip-width███░░░░░░
rank-width███████░░
shrub-depth██████░░░
sim-width█████░░░░
size███░░░░░░
slim tree-cut width██░░░░░░░
sparse twin-width██░░░░░░░
strong coloring number█████░░░░
strong d-coloring number████░░░░░
strong inf-coloring number███░░░░░░
topological bandwidth████░░░░░
tree-cut width██░░░░░░░
tree-independence number█████░░░░
tree-partition-width█████░░░░
treebandwidth████░░░░░
treedepth███████░░
treelength██████░░░
treespan███░░░░░░
treewidth█████████
twin-cover number█████░░░░
twin-width████████░
vertex connectivity░░░░░░░░░
vertex cover█████████
vertex integrity██████░░░
weak coloring number█████░░░░
weak d-coloring number████░░░░░
weak inf-coloring number███░░░░░░
weakly sparse and merge width░░░░░░░░░

Graph classes and Properties

Some parameters are derived from associated graph classes. Graph classes can be also used as witnesses of proper inclusions. For these purposes, we use the following graph class hierarchy. We assume that all of the graph class inclusions are proper.

We aim to have here only the graph classes that influence parameter inclusions. Please, see Information System on Graph Classes and their Inclusions (ISGCI) for an exhaustive list of graph classes and their inclusions.

Hasse graphs and properties (source)

Graph class*Relevance
bipartite████████░
block███░░░░░░
chordal██████░░░
cluster██████░░░
co-cluster██████░░░
cograph███████░░
complete█████████
cycle██░░░░░░░
cycles████░░░░░
forest█████████
grid██████░░░
interval███████░░
linear forest████░░░░░
outerplanar█████░░░░
path███░░░░░░
perfect██████░░░
planar████████░
series-parallel██████░░░
star███░░░░░░
stars████░░░░░
tree███████░░
Property*Relevance
bounded expansion██████░░░
chi-bounded█████░░░░
connected██░░░░░░░
edgeless█░░░░░░░░
excluded minor████░░░░░
excluded planar minor████░░░░░
excluded top-minor███░░░░░░
monadically dependent█████░░░░
monadically stable█████░░░░
nowhere dense█████░░░░
weakly sparse███░░░░░░

Sources

#Year*RelevanceSource
0002025████░░░░░On a tree-based variant of bandwidth and forbidding simple topological minors by Jacob, Lochet, Paul
0012024███░░░░░░Parameterized complexity for iterated type partitions and modular-width by Cordasco, Gargano, Rescigno
0022024██░░░░░░░Twin-width of graphs on surfaces by Kráľ, Pekárková, Štorgel
0032023█░░░░░░░░On Algorithmic Applications of Sim-Width and Mim-Width of $(H_1,H_2)$-Free Graphs by Munaro, Yang
0042024███████░░Merge-width and First-Order Model Checking by Dreier, Toruńczyk
0052024█████░░░░Slim Tree-Cut Width by Ganian, Korchemna
0062023███████░░Flip-width: Cops and Robber on dense graphs by Toruńczyk
0072022███████░░Expanding the Graph Parameter Hierarchy by Tran
0082022████░░░░░Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts by Brand, Ceylan, Ganian, Hatschka, Korchemna
0092021██████░░░Twin-width I: Tractable FO Model Checking by Bonnet, Kim, Thomassé, Watrigant
0102022██████░░░Excluding a Ladder by Huynh, Joret, Micek, Seweryn, Wollan
011unknown███████░░Comparing Graph Parameters by Schröder
0122020█░░░░░░░░Mim-Width I. Induced path problems by Jaffke, Kwon, Telle
0132019███████░░The Graph Parameter Hierarchy by Sorge
0142019█████░░░░Shrub-depth: Capturing Height of Dense Graphs by Ganian, Hliněný, Nešetřil, Obdržálek, Ossona de Mendez
0152018█░░░░░░░░A systematic comparison of graph parameters by Frömmrich
0162017███████░░Graph Theory by Diestel
0172015█████████Parameterized Algorithms by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh
0182015████░░░░░Improving Vertex Cover as a Graph Parameter by Ganian
0192015██░░░░░░░Linear rank-width and linear clique-width of trees by Adler, Kanté
0202015███░░░░░░The structure of graphs not admitting a fixed immersion by Wollan
0212013█░░░░░░░░The Power of Data Reduction: Kernels for Fundamental Graph Problems by Jansen
0222013█░░░░░░░░Characterizing graphs of small carving-width by Belmonte, van ’t Hof, Kamiński, Paulusma, Thilikos
0232013███░░░░░░Parameterized Algorithms for Modular-Width by Gajarský, Lampis, Ordyniak
0242012███░░░░░░New Width Parameters of Graphs by Vatshelle
0252012████░░░░░Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
0262012████░░░░░Classes of graphs with small rank decompositions are χ-bounded by Dvořák, Král’
0272012█░░░░░░░░Algorithmic Meta-theorems for Restrictions of Treewidth by Lampis
0282011████░░░░░Boolean-width of graphs by Bui-Xuan, Telle, Vatshelle
0292011██░░░░░░░Chordal Bipartite Graphs with High Boxicity by Chandran, Francis, Mathew
0302010███████░░Comparing 17 graph parameters by Sasák
0312010█░░░░░░░░The rank-width of the square grid by Jelínek
0322009███░░░░░░On tree-partition-width by Wood
0332009██░░░░░░░Clique-Width is NP-Complete by Fellows, Rosamond, Rotics, Szeider
0342008███░░░░░░Grad and classes with bounded expansion II. Algorithmic aspects by Nešetřil, Ossona de Mendez
0352008██░░░░░░░Spanning Trees with Many Leaves and Average Distance by DeLaViña, Waller
0362008██░░░░░░░Simulating Quantum Computation by Contracting Tensor Networks by Markov, Shi
0372007████░░░░░Graph Treewidth and Geometric Thickness Parameters by Dujmovic, Wood
0382006████░░░░░Approximating clique-width and branch-width by Oum, Seymour
0392005███░░░░░░On the relationship between NLC-width and linear NLC-width by Gurski, Wanke
0402005████░░░░░Graph Searching, Elimination Trees, and a Generalization of Bandwidth by Fomin, Heggernes, Telle
0412004███░░░░░░Track Layouts of Graphs by Dujmović, Pór, Wood
0422000█████░░░░Upper bounds to the clique width of graphs by Courcelle, Olariu
0431999████░░░░░A note on domino treewidth by Bodlaender
0441998███░░░░░░Clique-decomposition, NLC-decomposition and modular decomposition—relationships and results for random graphs by Johansson
0451998██████░░░A partial $k$-arboretum of graphs with bounded treewidth by Bodlaender
0461997█████░░░░Domino Treewidth by Bodlaender, Engelfriet
0471994███░░░░░░k-NLC graphs and polynomial algorithms by Wanke
0481993█████░░░░The Pathwidth and Treewidth of Cographs by Bodlaender, Möhring
0491991███████░░Graph minors. X. Obstructions to tree-decomposition by Robertson, Seymour
0501986███░░░░░░Graph minors. V. Excluding a planar graph by Robertson, Seymour
0511994██░░░░░░░Genus $g$ Graphs Have Pagenumber $O(\sqrt g)$ by Malitz
0521993████░░░░░On the chordality of a graph by McKee, Scheinerman
0531989███░░░░░░On dimensional properties of graphs by Cozzens, Roberts
0541986████████░Graph minors. II. Algorithmic aspects of tree-width by Robertson, Seymour
0551988█░░░░░░░░The average distanceisnot morethan the independence number by Chung
0561985█░░░░░░░░On the Cutwidth and the Topological Bandwidth of a Tree by Chung

Tags