A tight lower bound on the maximum genus of a 3-connected loopless multigraph (Q1595254): Difference between revisions

Let \(B(G)\) denote the cycle rank of a graph \(G\). The authors show that every 3-connected loopless multigraph \(G\) with \(B(G)< 10\) is upper-imbeddable; if \(B(G)\geq 10\), then the maximum genus of \(G\) is at least \(B(G)/3+ 1\). The lower bound is tight: there are infinitely many 3-connected loopless multigraphs attaining this bound.