Classification of Minimal Graphs of Given Face-Width on the Torus

✍ Scribed by A. Schrijver

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 666 KB
• Volume: 61
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1994.1046

✦ Synopsis

For any graph (G) embedded on the torus, the face-width (r(G)) of (G) is the minimum number of intersections of (G) and (C), where (C) ranges over all nonnullhomotopic closed curves on the torus. We call (G r)-minimal if (r(G) \geqslant r) and (r\left(G^{\prime}\right)<r) for each proper minor (G^{\prime}) of (G). We classify the (r)-minimal graphs by means of certain symmetric integer polygons in the plane (\mathbb{R}^{2}). Up to a certain natural equivalence, the number of (r)-minimal graphs on the torus is equal to (\frac{1}{6} r^{3}+\frac{5}{6} r) if (r) is odd and to (\frac{1}{6} r^{3}+\frac{4}{3} r) if (r) is even. 1994 Academic Press, Inc.