Extremal embedded graphs

Qi Yan, Xian'an Jin


Let G be a ribbon graph and μ(G) be the number of components of the virtual link formed from G as a cellularly embedded graph via the medial construction. In this paper we first prove that μ(G) ≤ f(G) + γ(G), where f(G) and γ(G) are the number of boundary components and Euler genus of G, respectively. A ribbon graph is said to be extremal if μ(G) = f(G) + γ(G). We then obtain that a ribbon graph is extremal if and only if its Petrial is plane. We introduce a notion of extremal minor and provide an excluded extremal minor characterization for extremal ribbon graphs. We also point out that a related result in the monograph by Ellis-Monaghan and Moffatt is not correct and prove that two related conjectures raised by Huggett and Tawfik hold for more general ribbon graphs.


Ribbon graph, medial graph, Petrie dual, extremal minor, orientation

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1474.d54

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications