Embeddings of bipartite graphs

Publisher Website
Google Scholar
Abstract
If G is a bipartite graph with bipartition A, B then let Gm,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a1, …, am, each vertex b of B by an independent set b1,…, bn, and each edge ab of G by the complete bipartite graph with edges aibj (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of Gm,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess‐current graphs.” They include new genus embeddings for a large class of bipartite graphs.

This publication has 9 references indexed in Scilit: