Maximal Planar (Bipartite) Graphs as Chordal (Bipartite) Graphs

Terry A. McKee1
1Department of Mathematics & Statistics Wright State University, Dayton, Ohio 45435 U.S.A.

Abstract

Among the well-studied maximal planar graphs, those having the maximum possible number of 3-cycles are precisely the planar chordal graphs (meaning no induced cycles of lengths greater than three). This motivates a somewhat similar result connecting maximal planar bipartite graphs, 4-cycles, and planar chordal bipartite graphs (meaning bipartite with no induced cycles of lengths greater than four), together with characterizations of planar chordal bipartite graphs as radial graphs of outerplanar multigraphs.