Face-width of embedded graphs (Q2702745)

The face-width of a graph embedded in a surface is the smallest number of points that the graph has in common with a noncontractible closed curve. Robertson and Seymour introduced this concept as a measure of how dense the graph is on the surface. The reviewer found a polynomial time algorithm for determining the face-width, and Robertson and Vitray proved that embeddings of large face-width are always minimum genus embeddings, and that they share many properties with planar embeddings. The subjects which are treated in detail in the present survey include face-width \(2\) or \(3\), graphs which are minimal in the sense that every minor has smaller face-width, embedding flexibility, uniqueness of embeddings, orientable genus of nonorientable embeddings, and combinatorial properties of embeddings of large width. Some unsolved problems are included. NEWLINENEWLINENEWLINEThe last one, Conjecture 9.7 has recently been proved in a joint work by T. Böhme, the author, and the reviewer. The same subjects are treated in a forthcoming book by the author and the reviewer.