Decomposing graphs into components with low genus

26 Views Asked by At

Graph parameters like treewidth and genus can be understood as 'measures of connectivity'. A feature in common between classes of graphs with bounded genus and classes with bounded treewidth is that both can be equivalently defined as classes of graphs with excluded minor.

Treewidth of a graph $G$ is usually understood in terms of a decomposition of the vertex set $V(G)$ into blocks which can be arranged as the vertices of the tree so that each vertex of $G$ is contained in a block and for any $v\in V(G)$, the blocks containing $v$ form a connected path. The treewidth of $G$ is at most $k$ if there is such a decomposition with blocks of size at most $k+1$.

Equivalently, the treewidth of $G$ can be understood in terms of a pursuit evasion game on $G$ where a player controls a set of $k$ cops and another player controls a robber who is allowed to move only on paths of $G$. The rules of the game are defined so that the player controlling the $k$ cops has a winning strategy if, and only if, the treewidth of $G$ is at most $k+1$.

My question is: can one define the class of graphs of genus at most $k$ in a similar manner using decompositions and/or a pursuit evasion game on the graphs?

For example, for the decomposition I envision would split the vertex set $V(G)$ into blocks of size at most $k$ which form the vertex set of a planar graph $G'$, and for each $v\in V(G)$, the blocks containing $v$ induce a connected subgraph of $G'$.