Classification of minimal graphs of given face-width on the torus
type: Item
instance of: scholarly article
title: Classification of minimal graphs of given face-width on the torus
zbMATH Open document ID: 0809.05036
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-03-20T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/2253
review text: The face-width of a graph embedded on the torus is the smallest \(n\) such that there is a noncontractible cycle on the torus which intersects the graph in exactly \(n\) points. This embedded graph is minimal if deleting or contracting any edge decreases the face-width. It is \(r\)-minimal if it is minimal with face-width \(r\). In this paper the author finds a correspondence between \(r\)-minimal toroidal graphs and certain polygons in the real plane. These polygons have integer coordinates and are symmetric about the origin. This correspondence gives a classification of the \(r\)-minimal graphs. Moreover, it allows the author to count, up to a natural equivalence, the number of \(r\)-minimal embedded graphs. This number is \(r^ 3/6+ 4r/3\) for \(r\) even and \(r^ 3/6+ 5r/6\) for \(r\) odd. The relationship between the face-width of a toroidal graph and the geometry of the plane integer lattice is beautiful. The reviewer strongly recommends reading this paper.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 52B20
zbMATH DE Number: 638662
zbMATH Keywords: face-width
zbMATH Keywords: torus
zbMATH Keywords: noncontractible cycle
zbMATH Keywords: embedded graph
zbMATH Keywords: toroidal graphs
zbMATH Keywords: polygons
zbMATH Keywords: plane integer lattice
reviewed by: Dan S. Archdeacon
MaRDI profile type: Publication
OpenAlex ID: W2046843026
DOI: 10.1006/JCTB.1994.1046
author: Alexander Schrijver
description: scientific article; zbMATH DE number 638662