genus
tags: topology
providers: ISGCI
Definition: Genus is the minimum integer $k$ such that the graph can be embedded on a surface with $k$ handles without edge crossings.
Relations
Other | Relation from | Relation to | |
---|---|---|---|
acyclic chromatic number | ■ | exclusion | upper bound |
admissibility | ■ | exclusion | upper bound |
arboricity | ■ | exclusion | upper bound |
average degree | ■ | exclusion | upper bound |
average distance | ■ | exclusion | exclusion |
bandwidth | ■ | exclusion | exclusion |
bipartite | ■ | unbounded | exclusion |
bipartite number | ■ | exclusion | exclusion |
bisection bandwidth | ■ | exclusion | exclusion |
block | ■ | unbounded | exclusion |
book thickness | ■ | exclusion | upper bound |
boolean width | ■ | exclusion | exclusion |
bounded components | ■ | unknown to HOPS | exclusion |
bounded expansion | ■ | exclusion | upper bound |
boxicity | ■ | exclusion | upper bound |
branch width | ■ | exclusion | exclusion |
c-closure | ■ | exclusion | exclusion |
carving-width | ■ | exclusion | exclusion |
chi-bounded | ■ | exclusion | unknown to HOPS |
chordal | ■ | unbounded | exclusion |
chordality | ■ | exclusion | upper bound |
chromatic number | ■ | exclusion | upper bound |
clique cover number | ■ | exclusion | exclusion |
clique-tree-width | ■ | exclusion | exclusion |
clique-width | ■ | exclusion | exclusion |
cluster | ■ | unbounded | exclusion |
co-cluster | ■ | unbounded | exclusion |
cograph | ■ | unbounded | exclusion |
complete | ■ | unbounded | exclusion |
connected | ■ | exclusion | avoids |
contraction complexity | ■ | exclusion | exclusion |
cutwidth | ■ | exclusion | exclusion |
cycle | ■ | upper bound | exclusion |
cycles | ■ | unknown to HOPS | exclusion |
d-admissibility | ■ | exclusion | upper bound |
d-path-free | ■ | exclusion | exclusion |
degeneracy | ■ | exclusion | upper bound |
degree treewidth | ■ | exclusion | exclusion |
diameter | ■ | exclusion | exclusion |
diameter+max degree | ■ | unknown to HOPS | exclusion |
distance to bipartite | ■ | exclusion | exclusion |
distance to block | ■ | exclusion | exclusion |
distance to bounded components | ■ | exclusion | exclusion |
distance to chordal | ■ | exclusion | exclusion |
distance to cluster | ■ | exclusion | exclusion |
distance to co-cluster | ■ | exclusion | exclusion |
distance to cograph | ■ | exclusion | exclusion |
distance to complete | ■ | exclusion | exclusion |
distance to edgeless | ■ | exclusion | exclusion |
distance to forest | ■ | exclusion | exclusion |
distance to interval | ■ | exclusion | exclusion |
distance to linear forest | ■ | exclusion | exclusion |
distance to maximum degree | ■ | exclusion | exclusion |
distance to outerplanar | ■ | exclusion | exclusion |
distance to perfect | ■ | exclusion | exclusion |
distance to planar | ■ | exclusion | exclusion |
distance to stars | ■ | exclusion | exclusion |
domatic number | ■ | exclusion | upper bound |
domination number | ■ | exclusion | exclusion |
domino treewidth | ■ | exclusion | exclusion |
edge clique cover number | ■ | exclusion | exclusion |
edge connectivity | ■ | exclusion | upper bound |
edge-cut width | ■ | unknown to HOPS | exclusion |
edge-treewidth | ■ | exclusion | exclusion |
edgeless | ■ | upper bound | avoids |
excluded minor | ■ | unknown to HOPS | upper bound |
excluded planar minor | ■ | unknown to HOPS | avoids |
excluded top-minor | ■ | exclusion | upper bound |
feedback edge set | ■ | upper bound | exclusion |
feedback vertex set | ■ | exclusion | exclusion |
flip-width | ■ | exclusion | upper bound |
forest | ■ | upper bound | exclusion |
genus | ■ | equal | equal |
grid | ■ | upper bound | exclusion |
h-index | ■ | exclusion | exclusion |
interval | ■ | unbounded | exclusion |
iterated type partitions | ■ | exclusion | exclusion |
linear clique-width | ■ | exclusion | exclusion |
linear forest | ■ | upper bound | exclusion |
linear NLC-width | ■ | exclusion | exclusion |
linear rank-width | ■ | exclusion | exclusion |
maximum clique | ■ | exclusion | upper bound |
maximum degree | ■ | exclusion | exclusion |
maximum independent set | ■ | exclusion | exclusion |
maximum induced matching | ■ | exclusion | exclusion |
maximum leaf number | ■ | upper bound | exclusion |
maximum matching | ■ | exclusion | exclusion |
maximum matching on bipartite graphs | ■ | unknown to HOPS | exclusion |
merge-width | ■ | exclusion | upper bound |
mim-width | ■ | exclusion | unknown to HOPS |
minimum degree | ■ | exclusion | upper bound |
mm-width | ■ | exclusion | exclusion |
modular-width | ■ | exclusion | exclusion |
module-width | ■ | exclusion | exclusion |
monadically dependent | ■ | exclusion | upper bound |
monadically stable | ■ | exclusion | upper bound |
neighborhood diversity | ■ | exclusion | exclusion |
NLC-width | ■ | exclusion | exclusion |
NLCT-width | ■ | exclusion | exclusion |
nowhere dense | ■ | exclusion | upper bound |
odd cycle transversal | ■ | exclusion | exclusion |
outerplanar | ■ | upper bound | exclusion |
overlap treewidth | ■ | exclusion | exclusion |
path | ■ | upper bound | exclusion |
pathwidth | ■ | exclusion | exclusion |
pathwidth+maxdegree | ■ | exclusion | exclusion |
perfect | ■ | unbounded | exclusion |
planar | ■ | upper bound | exclusion |
radius-inf flip-width | ■ | exclusion | exclusion |
radius-r flip-width | ■ | exclusion | upper bound |
rank-width | ■ | exclusion | exclusion |
series-parallel | ■ | unknown to HOPS | unknown to HOPS |
shrub-depth | ■ | exclusion | exclusion |
sim-width | ■ | exclusion | unknown to HOPS |
size | ■ | upper bound | exclusion |
slim tree-cut width | ■ | exclusion | exclusion |
sparse twin-width | ■ | exclusion | upper bound |
star | ■ | upper bound | exclusion |
stars | ■ | upper bound | exclusion |
strong coloring number | ■ | exclusion | upper bound |
strong d-coloring number | ■ | exclusion | upper bound |
strong inf-coloring number | ■ | exclusion | exclusion |
topological bandwidth | ■ | exclusion | exclusion |
tree | ■ | upper bound | exclusion |
tree-cut width | ■ | exclusion | exclusion |
tree-independence number | ■ | exclusion | unknown to HOPS |
tree-partition-width | ■ | exclusion | exclusion |
treebandwidth | ■ | exclusion | exclusion |
treedepth | ■ | exclusion | exclusion |
treelength | ■ | exclusion | unknown to HOPS |
treespan | ■ | exclusion | exclusion |
treewidth | ■ | exclusion | exclusion |
twin-cover number | ■ | exclusion | exclusion |
twin-width | ■ | exclusion | upper bound |
vertex connectivity | ■ | unknown to HOPS | unknown to HOPS |
vertex cover | ■ | exclusion | exclusion |
vertex integrity | ■ | exclusion | exclusion |
weak coloring number | ■ | exclusion | upper bound |
weak d-coloring number | ■ | exclusion | upper bound |
weak inf-coloring number | ■ | exclusion | exclusion |
weakly sparse | ■ | exclusion | upper bound |
weakly sparse and merge width | ■ | exclusion | upper bound |
Results
- 2024 Twin-width of graphs on surfaces by Kráľ, Pekárková, Štorgel
- page 18 : genus upper bounds twin-width by a linear function – The twin-width of every graph $G$ of Euler genus $g \ge 1$ is at most … $18 \sqrt{47g}+O(1)$.
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- page 34 : graph classes with bounded c-closure are not bounded genus – Proposition 5.6. $c$-Closure is incomparable to Genus.
- page 34 : graph classes with bounded genus are not bounded c-closure – Proposition 5.6. $c$-Closure is incomparable to Genus.
- page 37 : genus upper bounds twin-width by a linear function – Proposition 6.3. Genus strictly upper bounds Twin-width.
- page 37 : graph classes with bounded twin-width are not bounded genus – Proposition 6.3. Genus strictly upper bounds Twin-width.
- 2019 The Graph Parameter Hierarchy by Sorge
- page 8 : genus upper bounds acyclic chromatic number by a linear function – Lemma 4.8 ([3]). The accylic chromatic number $\chi_a$ is upper bounded by the genus $g$. We have $\chi_a \le 4g+4$.
- page 10 : feedback edge set upper bounds genus by a linear function – Lemma 4.19. The feedback edge set number $f$ upper bounds the genus $g$. We have $g \le f$.
- 1994 Genus $g$ Graphs Have Pagenumber $O(\sqrt g)$ by Malitz
- page 24 : genus upper bounds book thickness by a linear function – Theorem 5.1. Genus $g$ graphs have pagenumber $O(\sqrt{g})$.
- assumed
- unknown source
- feedback edge set upper bounds genus by a linear function – Removing $k$ edges creates a forest that is embeddable into the plane. We now add one handle for each of the $k$ edges to get embedding into $k$-handle genus.
- planar upper bounds genus by a constant
- genus upper bounds chromatic number by a constant – in fact, bounded by square root
- genus upper bounds excluded minor by a computable function
- Comparing Graph Parameters by Schröder
- page 23 : graph classes with bounded genus are not bounded clique-width – Proposition 3.17
- page 24 : graph classes with bounded vertex cover are not bounded genus – Proposition 3.18
- page 26 : graph classes with bounded genus are not bounded distance to perfect – Proposition 3.24
- page 30 : graph classes with bounded bandwidth are not bounded genus – Proposition 3.27
- page 33 : graph classes with bounded genus are not bounded distance to planar – Proposition 3.34