Excluding Graphs as Immersions in Surface Embedded Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Preprints, Working Papers, ... Year : 2013

Excluding Graphs as Immersions in Surface Embedded Graphs

Abstract

We prove a structural characterization of graphs that forbid a fixed graph $H$ as an immersion and can be embedded in a surface of Euler genus $\gamma$. In particular, we prove that a graph $G$ that excludes some connected graph $H$ as an immersion and is embedded in a surface of Euler genus $\gamma$ has either "small" treewidth (bounded by a function of $H$ and $\gamma$) or "small" edge connectivity (bounded by the maximum degree of $H$). Using the same techniques we also prove an excluded grid theorem on bounded genus graphs for the immersion relation.

Dates and versions

lirmm-00805139 , version 1 (27-03-2013)

Identifiers

  • HAL Id : lirmm-00805139 , version 1
  • ARXIV : 1303.6567

Cite

Archontia C. Giannopoulou, Marcin Kaminski, Dimitrios M. Thilikos. Excluding Graphs as Immersions in Surface Embedded Graphs. 2013. ⟨lirmm-00805139⟩
101 View
0 Download

Altmetric

Share

More