@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",

}