Map Number

The map number of a graph is the least nonnegative integer for which is a -map graph. Such a representation consists of closed regions on the sphere, each homeomorphic to a closed disk, with disjoint interiors. Two regions are adjacent exactly when their boundaries share a point, and at most regions meet at any point. Write this quantity as , with when is not a map graph.

Equivalently, it is the minimum possible largest auxiliary vertex degree in a planar bipartite graph whose original vertices are adjacent in iff they share an auxiliary neighbor. Each original vertex must have at least one such neighbor (Chen et al. 1999, Theorem 2.2).

The null graph has map number 0, a nonempty empty graph has map number 1, and a planar graph with an edge has map number 2. No graph has map number 3. A -free graph is a map graph iff it is a planar graph, where is the complete graph on four vertices.

For a nonplanar graph with finite map number and clique number , , where is the ceiling function (Chen et al. 1999, Theorem 2.7). Map number cannot increase on taking an induced subgraph. For a nonempty disconnected graph, it is the maximum of the map numbers of its connected components.

Special cases are given below. Here , , , , and denote the complete graph, barbell graph, complete bipartite graph, complete tripartite graph, and hypercube graph, respectively. Write for the king graph and for the rook graph on an board. Take for , , and , and for . The remaining domains are for , for , and for . For a grid graph , discard dimensions of size one and sort the remaining sizes as .

			(1)
			(2)
			(3)
			(4)
			(5)
			(6)
			(7)
			(8)