Quasi-Surfaces and Three Different Types of Graph Embeddings
We continue discussing about the quasi-surface, which is a generalization of both the k-book space and the 2-sphere. This time, we focus on how to embed graphs on the quasi-surface with respect to the event horizon; there are three different types of embeddings: (i) the 2-cell embedding, (ii) embedding no edge crossing on the event horizon, and (iii) no restriction on the event horizon. Note that every book embedding can be generalized to the types (ii) and (iii), but not to (i). Similar to the book thickness or page number of a graph, we define the shell number of a graph for each embedding type. It is known that determining the exact page number of a graph is difficult even for complete bipartite graphs. On the other hand, the shell number of K_{m,n} for type (i) can be determined for arbitrary m and n in the talk.