@inproceedings{aa49b20900f94b87860c794d6ba11e7b,
title = "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 γ. 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 γ has either {"}small{"} treewidth (bounded by a function of H and γ) 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.",
keywords = "Edge Connectivity, Immersion Relation, Surface Embeddable Graphs, Treewidth",
author = "Giannopoulou, {Archontia C.} and Marcin Kami{\'n}ski and Thilikos, {Dimitrios M.}",
year = "2013",
doi = "10.1007/978-3-642-45043-3_24",
language = "English (US)",
isbn = "9783642450426",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "274--285",
booktitle = "Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Revised Papers",
note = "39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013 ; Conference date: 19-06-2013 Through 21-06-2013",
}