Let $P$ be a set of points in the plane. In the Gabriel graph of $P$ there is an edge between $p$ and $q$ iff the circle having
$pq$ as a diameter contains no other point of $P$.
A graph is a Gabriel graph if it is the Gabriel graph of some set of points in the plane.
For a fixed set of points we have the following relations between edges: relative neighbourhood graph $\subseteq$ Urquhart $\subseteq$ Gabriel $\subseteq$ Delaunay
The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.
acyclic chromatic number
[?]
The acyclic chromatic number of a graph $G$ is the smallest size of a vertex partition $\{V_1,\dots,V_l\}$ such that each $V_i$ is an independent set
and for all $i,j$ that graph $G[V_i\cup V_j]$ does not contain a cycle.

Bounded  [+]Details  
bandwidth
[?]
The bandwidth of a graph $G$ is the shortest maximum "length" of an edge over all one dimensional layouts of $G$. Formally, bandwidth is defined as $\min_{i \colon V \rightarrow \mathbb{N}\;}\{\max_{\{u,v\}\in E\;} \{i(u)i(v)\}\mid i\text{ is injective}\}$.

Unknown to ISGCI  [+]Details  
book thickness
[?]
A book embedding of a graph $G$ is an embedding of $G$ on a collection of halfplanes (called pages) having the same line
(called spine) as their boundary, such that the vertices all lie on the spine and there are no crossing edges. The book thickness of a graph $G$ is the smallest number of pages over all book embeddings of $G$.

Bounded  [+]Details  
booleanwidth
[?]
Consider the following decomposition of a graph $G$ which is defined as a pair $(T,L)$ where $T$ is a binary tree and $L$
is a bijection from $V(G)$ to the leaves of the tree $T$. The function $\text{cutbool} \colon 2^{V(G)} \rightarrow R$ is
defined as $\text{cutbool}(A)$ := $\log_2\{S \subseteq V(G) \backslash A \mid \exists X \subseteq A \colon S = (V(G) \backslash
A) \cap \bigcup_{x \in X} N(x)\}$. Every edge $e$ in $T$ partitions the vertices $V(G)$ into $\{A_e,\overline{A_e}\}$ according
to the leaves of the two connected components of $T  e$. The booleanwidth of the above decomposition $(T,L)$ is $\max_{e
\in E(T)\;} \{ \text{cutbool}(A_e)\}$. The booleanwidth of a graph $G$ is the minimum booleanwidth of a decomposition of $G$ as above.

Unknown to ISGCI  [+]Details  
branchwidth
[?]
A branch decomposition of a graph $G$ is a pair $(T,\chi)$, where $T$ is a binary tree and $\chi$ is a bijection, mapping
leaves of $T$ to edges of $G$. Any edge $\{u, v\}$ of the tree divides the tree into two components and divides the set of
edges of $G$ into two parts $X, E \backslash X$, consisting of edges mapped to the leaves of each component. The width of
the edge $\{u,v\}$ is the number of vertices of $G$ that is incident both with an edge in $X$ and with an edge in $E \backslash
X$. The width of the decomposition $(T,\chi)$ is the maximum width of its edges. The branchwidth of the graph $G$ is the minimum width over all branchdecompositions of $G$.

Unknown to ISGCI  [+]Details  
carvingwidth
[?]
Consider a decomposition $(T,\chi)$ of a graph $G$ where $T$ is a binary tree with $V(G)$ leaves and $\chi$ is a bijection
mapping the leaves of $T$ to the vertices of $G$. Every edge $e \in E(T)$ of the tree $T$ partitions the vertices of the graph
$G$ into two parts $V_e$ and $V \backslash V_e$ according to the leaves of the two connected components in $T  e$. The width
of an edge $e$ of the tree is the number of edges of a graph $G$ that have exactly one endpoint in $V_e$ and another endpoint
in $V \backslash V_e$. The width of the decomposition $(T,\chi)$ is the largest width over all edges of the tree $T$. The
carvingwidth of a graph is the minimum width over all decompositions as above.

Unknown to ISGCI  [+]Details  
chromatic number
[?]
The chromatic number of a graph is the minimum number of colours needed to label all its vertices in such a way that no two vertices with the
same color are adjacent.

Bounded  [+]Details  
cliquewidth
[?]
The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:

Unknown to ISGCI  [+]Details  
cochromatic number
[?]
The cochromatic number of a graph $G$ is the minimum number of colours needed to label all its vertices in such a way that that every set of vertices
with the same colour is either independent in G, or independent in $\overline{G}$.

Bounded  [+]Details  
cutwidth
[?]
The cutwidth of a graph $G$ is the smallest integer $k$ such that the vertices of $G$ can be arranged in a linear layout $v_1,
\ldots, v_n$ in such a way that for every $i = 1, \ldots,n  1$, there are at most $k$ edges with one endpoint in $\{v_1,
\ldots, v_i\}$ and the other in ${v_{i+1}, \ldots, v_n\}$.

Unknown to ISGCI  [+]Details  
degeneracy
[?]
Let $G$ be a graph and consider the following algorithm:

Bounded  [+]Details  
diameter
[?]
The diameter of a graph $G$ is the length of the longest shortest path between any two vertices in $G$.

Unknown to ISGCI  [+]Details  
distance to block
[?]
The distance to block of a graph $G$ is the size of a smallest vertex subset whose deletion makes $G$ a block graph.

Unknown to ISGCI  [+]Details  
distance to clique
[?]
Let $G$ be a graph. Its distance to clique is the minimum number of vertices that have to be deleted from $G$ in order to obtain a clique.

Unknown to ISGCI  [+]Details  
distance to cluster
[?]
A cluster is a disjoint union of cliques. The distance to cluster of a graph $G$ is the size of a smallest vertex subset whose deletion makes $G$ a cluster graph.

Unknown to ISGCI  [+]Details  
distance to cocluster
[?]
The distance to cocluster of a graph is the minimum number of vertices that have to be deleted to obtain a cocluster graph.

Unknown to ISGCI  [+]Details  
distance to cograph
[?]
The distance to cograph of a graph $G$ is the minimum number of vertices that have to be deleted from $G$ in order to obtain a cograph .

Unknown to ISGCI  [+]Details  
distance to linear forest
[?]
The distance to linear forest of a graph $G = (V, E)$ is the size of a smallest subset $S$ of vertices, such that $G[V \backslash S]$ is a disjoint union
of paths and singleton vertices.

Unknown to ISGCI  [+]Details  
distance to outerplanar
[?]
The distance to outerplanar of a graph $G = (V,E)$ is the minumum size of a vertex subset $X \subseteq V$, such that $G[V \backslash X]$ is a outerplanar graph.

Unknown to ISGCI  [+]Details  
genus
[?]
The genus $g$ of a graph $G$ is the minimum number of handles over all surfaces on which $G$ can be embedded without edge
crossings.

Bounded  [+]Details  
maxleaf number
[?]
The maxleaf number of a graph $G$ is the maximum number of leaves in a spanning tree of $G$.

Unknown to ISGCI  [+]Details  
maximum clique
[?]
The parameter maximum clique of a graph $G$ is the largest number of vertices in a complete subgraph of $G$.

Bounded  [+]Details  
maximum degree
[?]
The maximum degree of a graph $G$ is the largest number of neighbors of a vertex in $G$.

Unknown to ISGCI  [+]Details  
maximum independent set
[?]
An independent set of a graph $G$ is a subset of pairwise nonadjacent vertices. The parameter maximum independent set of graph $G$ is the size of a largest independent set in $G$.

Unknown to ISGCI  [+]Details  
maximum induced matching
[?]
For a graph $G = (V,E)$ an induced matching is an edge subset $M \subseteq E$ that satisfies the following two conditions:
$M$ is a matching of the graph $G$ and there is no edge in $E \backslash M$ connecting any two vertices belonging to edges
of the matching $M$. The parameter maximum induced matching of a graph $G$ is the largest size of an induced matching in $G$.

Unknown to ISGCI  [+]Details  
maximum matching
[?]
A matching in a graph is a subset of pairwise disjoint edges (any two edges that do not share an endpoint). The parameter
maximum matching of a graph $G$ is the largest size of a matching in $G$.

Unknown to ISGCI  [+]Details  
minimum clique cover
[?]
A clique cover of a graph $G = (V, E)$ is a partition $P$ of $V$ such that each part in $P$ induces a clique in $G$. The minimum clique cover of $G$ is the minimum number of parts in a clique cover of $G$. Note that the clique cover number of a graph is exactly the
chromatic number of its complement.

Unknown to ISGCI  [+]Details  
minimum dominating set
[?]
A dominating set of a graph $G$ is a subset $D$ of its vertices, such that every vertex not in $D$ is adjacent to at least
one member of $D$. The parameter minimum dominating set for graph $G$ is the minimum number of vertices in a dominating set for $G$.

Unknown to ISGCI  [+]Details  
pathwidth
[?]
A path decomposition of a graph $G$ is a pair $(P,X)$ where $P$ is a path with vertex set $\{1, \ldots, q\}$, and $X = \{X_1,X_2,
\ldots ,X_q\}$ is a family of vertex subsets of $V(G)$ such that:

Unknown to ISGCI  [+]Details  
rankwidth
[?]
Let $M$ be the $V \times V$ adjacency matrix of a graph $G$. The cut rank of a set $A \subseteq V(G)$ is the rank of the
submatrix of $M$ induced by the rows of $A$ and the columns of $V(G) \backslash A$. A rank decomposition of a graph $G$ is
a pair $(T,L)$ where $T$ is a binary tree and $L$ is a bijection from $V(G)$ to the leaves of the tree $T$. Any edge $e$ in
the tree $T$ splits $V(G)$ into two parts $A_e, B_e$ corresponding to the leaves of the two connected components of $T  e$.
The width of an edge $e \in E(T)$ is the cutrank of $A_e$. The width of the rankdecomposition $(T,L)$ is the maximum width
of an edge in $T$. The rankwidth of the graph $G$ is the minimum width of a rankdecomposition of $G$.

Unknown to ISGCI  [+]Details  
tree depth
[?]
A tree depth decomposition of a graph $G = (V,E)$ is a rooted tree $T$ with the same vertices $V$, such that, for every edge
$\{u,v\} \in E$, either $u$ is an ancestor of $v$ or $v$ is an ancestor of $u$ in the tree $T$. The depth of $T$ is the maximum
number of vertices on a path from the root to any leaf. The tree depth of a graph $G$ is the minimum depth among all tree depth decompositions.

Unknown to ISGCI  [+]Details  
treewidth
[?]
A tree decomposition of a graph $G$ is a pair $(T, X)$, where $T = (I, F)$ is a tree, and $X = \{X_i \mid i \in I\}$ is a
family of subsets of $V(G)$ such that
The treewidth of a graph is the minimum width over all possible tree decompositions of the graph. 
Unknown to ISGCI  [+]Details  
vertex cover
[?]
Let $G$ be a graph. Its vertex cover number is the minimum number of vertices that have to be deleted in order to obtain an independent set.

Unknown to ISGCI  [+]Details 
Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.
book thickness decomposition
[?]

Unknown to ISGCI  [+]Details  
booleanwidth decomposition
[?]

Unknown to ISGCI  [+]Details  
cliquewidth decomposition
[?]

Unknown to ISGCI  [+]Details  
cutwidth decomposition
[?]

Unknown to ISGCI  [+]Details  
treewidth decomposition
[?]

Unknown to ISGCI  [+]Details 
3Colourability
[?]

Unknown to ISGCI  [+]Details  
Clique
[?]

Polynomial  [+]Details  
Clique cover
[?]

Unknown to ISGCI  [+]Details  
Colourability
[?]

Unknown to ISGCI  [+]Details  
Domination
[?]

Unknown to ISGCI  [+]Details  
Feedback vertex set
[?]

Unknown to ISGCI  [+]Details  
Graph isomorphism
[?]

Linear  [+]Details  
Hamiltonian cycle
[?]

Unknown to ISGCI  [+]Details  
Hamiltonian path
[?]

Unknown to ISGCI  [+]Details  
Independent set
[?]

Unknown to ISGCI  [+]Details  
Maximum cut
[?]
(decision variant)

Polynomial  [+]Details  
Monopolarity
[?]

Unknown to ISGCI  [+]Details  
Polarity
[?]

Unknown to ISGCI  [+]Details  
Recognition
[?]

Unknown to ISGCI  [+]Details 
Weighted clique
[?]

Polynomial  [+]Details  
Weighted feedback vertex set
[?]

Unknown to ISGCI  [+]Details  
Weighted independent set
[?]

Unknown to ISGCI  [+]Details  
Weighted maximum cut
[?]
(decision variant)

Polynomial  [+]Details 