A catalog of facially complete graphs

<p>onsidering regions in a map to be adjacent when they have nonempty intersection (as opposed to the traditional view requiring intersection in a linear segment) leads to the concept of a <em>facially complete</em> graph: a plane graph that becomes complete when edges are added between every two vertices that lie on a face. Here we present a complete catalog of facially complete graphs: they fall into seven types. A consequence is that if <span class="math inline">\(q\)</span> is the size of the largest face in a plane graph <span class="math inline">\(G\)</span> that is facially complete, then <span class="math inline">\(G\)</span> has at most <span class="math inline">\(\left\lfloor 3q/2\right\rfloor\)</span> vertices. This bound was known, but our proof is completely different from the 1998 approach of Chen, Grigni, and Papadimitriou (Planar map graphs, <em>Proc. 30th ACM Symp. Th. of Computing</em>, 514–523). Our method also yields a count of the 2-connected facially complete graphs with <span class="math inline">\(n\)</span> vertices. We also show that if a plane graph has at most two faces of size 4 and no larger face, then the addition of both diagonals to each 4-face leads to a graph that is 5-colorable.</p>