On the crossing number of complete graphs: Growing minimal Kn from minimal Kn-1

This dissertation addresses the generation of minimal complete graphs. A complete graph, denoted Kn, is a graph in which each vertex is connected to every other vertex of the graph with an edge. A minimal graph is a representation of a graph that exhibits its crossing number. The crossing number of a graph is the smallest number of edge crossings over all planar representations of the graph.; Presented is a constructive framework for iteratively generating minimal Kn from minimal Kn -1. The process described allows for complete enumeration of all minimal Kn derivable from minimal Kn-1, including those graphs that are only locally minimal. A graph is locally minimal if it reflects the smallest number of crossings possible for a given region placement of vertex n in minimal Kn -1. All graphs are classified into isomorphic families, allowing for efficient iteration to the next set of complete graphs of order n + 1 due to needing only one representative from each K n isomorphic family for complete results.; In addition to determining the crossing number for Kn generated by Kn-1, all minimal graphs are available for exploration of their underlying structure. This allows for substructure isomorphic analysis and localized region neighborhood analysis, both of which will lead to yet more efficient iteration of K n for increasing n. Information culled from these graphs may also shed light on new or improved lower bound estimation techniques.; A seven-step process is presented that allows for iterative growth. The main module in the process, Star Analysis, takes a global view of growing minimal Kn by focusing on optimizing the enumeration of all star graphs, K1,n-1, centered at vertex n placed into initial minimal K n-1 at all possible different region locations.; This research introduces new conjectures and opens some new questions for exploring the structure of minimal Kn. Though this work focuses on minimal complete graphs, the process appears to be applicable to an assortment of other graph families. An example is presented of its application to complete bipartite graphs.