\chapter{Star Analysis}\label{ch3}
\section{Introduction}\label{sec:sai}
{
All the refinements introduced up to this point resulted in a system that quickly finds minimal graphs up to K$_9$, and finds K$_{10}$ minimal graphs in a runtime of approximately one week. Above K$_{10}$, the runtimes are anticipated to increase drastically. Generation of minimal K$_{10}$ requires that the process be run on fourteen hundred and fifty-three different (i.e. nonisomorphic) minimal K$_9$ graphs, each of which contains sixty-five regions. Generation of minimal K$_{11}$ begins with five thousand six hundred and seventy-nine nonisomorphic minimal K$_{10}$ graphs, each with 97 regions. So the quest for optimization of the process continues. 

A brief recap of the current state of the algorithm will facilitate the discussions that follow. Minimal K$_n$ graphs are created from representatives of each isomorphic family of K$_{n-1}$, beginning with K$_5$. As minimal K$_5$ only has one isomorphic family, only a single so-called "feeder" graph is needed to progress to minimal K$_6$. The algorithm begins by taking the feeder graph and numbering its vertices. Native vertices, those that are in fact in the graph's vertex set, are numbered from one to five. Number six is reserved for the new vertex to be added, and number seven is used to identify the single crossing vertex ( $\nu$(K$_5$) = $1$ ). 

The next step is to place vertex six into each of the eight regions of minimal K$_5$. This creates eight starting partial graphs, one of which is shown in Figure~\ref{fig:K5start}.

 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=3.0in]{ch3/K5start.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_5$ to K$_6$: K$_5$ Graph With New Vertex 6 Placed}
       \label{fig:K5start}
 \end{figure}
For each, a preprocessing step makes connections between vertex six and the native vertices bounding the region in which it was placed; in other words, any connections that can be made without new crossings (Figure~\ref{fig:K5InitConnect}).
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=3.0in]{ch3/K5InitConnect.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_5$ to K$_6$: Initial Connections}
       \label{fig:K5InitConnect}
 \end{figure}
Any connections not able to be completed directly are placed on an edges-to-add list. The partial graphs are then fed into the parallel processing system.

The parallel system begins by reading in all the partial graphs and edges-to-add lists. The master processor packages each pair of one graph and its associated list into a "job" packet and enqueues it on the master queue. It then distributes jobs to each of the slaves via MPI. Edges are created one segment at a time, where an edge segment is that portion of an edge that crosses a single region. All possible region passages, within the bounds of the radical region restriction definition of a good drawing, are tested. When an edge segment is laid down, it terminates on one of the edges of the region it has crossed, creating a new crossing vertex. After creating the segment and crossing vertex, the processor looks for the terminal connecting vertex, based on the edges-to-add list, in the new region across the crossing segment. Only the specific vertex being sought by that job will be connected to complete the edge. If that vertex is not found in the boundary of the new region, the processor packages the new partial graph into a job packet and places it on its own work queue. If a region has, say, three legal region-bounding edges to cross, three new jobs will be created and enqueued, each with one new edge segment and one new crossing vertex, as a result of following each path. Thus as multiple segments are placed, the number of job packets in the work queue grows. If the number exceeds a user-defined limit, excess packets are sent back to the master for redistribution. When all job queues are empty and all edges complete, the process terminates. The completed K$_6$ graph with (a) and without (b) crossing vertices labeled is shown in Figure~\ref{fig:K6complete}.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=3.0in]{ch3/K6complete.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_5$ to K$_6$: K$_6$ Complete}
       \label{fig:K6complete}
 \end{figure}

A key feature of the process is a preliminary step that provides the bound for the search. As described in Section~\ref{sec:rrr}, we want to take only those paths that are less than or equal to the length of the shortest possible path across the regions to each vertex. This number is determined by a scan of the graph before any edge segments are laid down. Nonetheless, all possible graphs are then built up to the point at which the minimum path length is exceeded. Building and then discarding all these nonminimal partial graphs generates a tremendous amount of extra, unnecessary processing, enqueuing, dequeuing, and message passing. We reasoned that the process could be expedited by not building any graphs at all, but rather by simply identifying the shortest paths to each vertex. By saving all paths, we would have the added advantage of identifying possibly important nonminimal paths for further study. We could then selectively choose which graphs to build based on criteria we could change. Eliminating all the laying down of edge segments also allows us to dispense with the parallel system as it currently exists, along with its massive overhead. 
}%\end section{Introduction}

\section{Overview of Algorithm}\label{sec:ooa}
{
The process of Star Analysis begins similarly to its predecessor. Representative graphs from each isomorphic family of K$_{n-1}$ are taken by a preprocessing program and prepared for evaluation by vertex numbering and inserting a new vertex, $n$, into each region of each representative graph. As opposed to the previous approach, direct connections are not made at this time, rather all edges are placed on the edges-to-add list. 

The second program in the Star Analysis module is run once for each feeder graph by a calling script. In each iteration, Star Analysis receives a graph in the form of a Region List (described below), the edges-to-add list, and the region number in which the new vertex should be placed. It examines all possible paths to connect the new vertex to each of the existing ones, placing the paths in a Path List. The completed Path List with all paths is saved to a file. Paths are created independently of each other and in no particular order.
	
A third program in the module generates the actual graphs. Again, a calling script is employed, which can be varied to select minimal paths only, minimal-plus-one paths, or any desired combination. Graphs resulting from each of the regional vertex placements that meet the chosen criteria are created. The graphs are again represented in the form of region lists, which are saved into files.

The next step is a program that takes the Region List representations of the graphs and converts them into adjacency matrices. Adjacency matrices are required by the $NAUTY$ program, which determines isomorphism among them and sorts them into isomorphic families. 	The final step is to pluck a representative of each isomorphic family from the sorted graphs and create files for the K$_n$ to K$_{n+1}$ run.
}%\end section{Overview of Algorithm}
 
\section{Data Structures}\label{sec:ds}
{
\subsection{Region List} \label{sec:rl}
{
The Region List class is adapted from that used previously by~\cite{Yuan2004:gqstsrrccnkn}, modified to function in the current Distance Tree environment. The Region List is constructed as a list of lists, where each sublist represents a single region of a graph. Individual regions are defined by the vertices along their boundaries. The Region List class provides a wealth of functionality for dealing with a region list. It facilitates adding and deleting regions or vertices within regions, examining regions for the presence of specific vertices, adding edges to a graph and updating the adjoining regions, and searching for regions based on a variety of parameters. An example of a starting K$_5$ graph with its Region List representation is shown in Figure~\ref{fig:K5RL}

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/K5RegionList.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A K$_5$ Graph with New Vertex 6 in Region 7 and its Associated Region List}
       \label{fig:K5RL}
 \end{figure}

}%\end subsection{Region List}

\subsection{Distance Tree}\label{sec:dt}
{
The program that analyzes the graphs for shortest paths is based on an object-oriented structure we have entitled a Distance Tree. A Distance Tree class object is a full tree; that is, each level of the tree is complete, and it is built breadth-first.
 
The tree is constructed of TreeNode class objects. A TreeNode object consists of five data members: a pair of vertices, representing an edge segment of the graph; a region number, representing the region that will be entered upon crossing the aforementioned edge; a vertex number, representing an end vertex if one is found in the region; a pointer that points to the parent node for back tracing when the path is complete; and an array of pointers pointing to nodes at the next level of the tree. 

The root of the tree represents the newly placed vertex; its TreeNode, at Level 0, has edge values (0,0), a region value representing the region it is in, an initial vertex number of 0, a NULL parent pointer and a list-of-pointers pointer for creating the downward branches of the tree, as yet unassigned (Refer to Figure~\ref{fig:beginDT}). Once this node is created, the program reads through the edges-to-add list to see if any edges can be completed without crossings. Any such edges are completed by updating the vertex value in the TreeNode to the number of the edge end vertex. The node is then used as a template to create a PathNode to be added to the Path List, described below. At the root level, the path to be added to the Path List as a sublist consists of a single PathNode. Any completed edges are removed from the edges-to-add list, and the program checks whether edges remain to be added. At the root level, there will always be additional edges to add since no crossings have occurred yet, so we proceed by adding the current region to a restricted region list and dynamically allocating memory for TreeNodes at the next level. TreeNode pointers point to new branches for each exit edge from the region, since all exits are legal from the root region.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/beginDT.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Snapshot of a K$_5$ to K$_6$ Distance Tree After Creating Level 1}
       \label{fig:beginDT}
 \end{figure}

At the next tree level, Level 1, a node is created for each new TreeNode pointer, as seen in Figure~\ref{fig:beginDT}. These are initialized with the edge that was crossed leaving the starting region, the new region that was entered, an initial vertex number of 0, a parent pointer pointing to the root node, and a list-of-pointers pointer as before. Once again we check for edges that can be completed, moving from node to node at the new level and scanning the edges-to-add list. One important difference, beginning with this level and continuing with all others, is that edges are not removed from the edges-to-add list until all nodes on the level have been visited. This is because all shortest paths to the vertices must be obtained, and all paths on the same level will have the same number of crossings, so no node further across on the level should be prevented from making a connection to a terminal vertex just because an earlier one already connected to it. If an edge can be completed, we create a path to attach to the Path List consisting of two PathNodes linked together; one based on the TreeNode at this level, and one based on its parent, obtained by following the parent pointer. At the end of the level, when all nodes have been visited, the edges-to-add list is updated. If the edges-to-add list is not empty, all the regions on the current level are added to the restricted region list, and nodes are dynamically allocated at the next level. New nodes are created for all edges that can be legally crossed from each current region, which are the ones that lead to regions not found on the restricted regions list.
 
This process continues, with new levels and nodes being created, until the edges-to-add list is empty, and all paths have been transferred to the Path List. A final point is that the restricted region list is not updated until after each level is complete, since it is both possible and legal for two edges to enter the same region at the same level from different directions. A potential problem arises if these edges cross before exiting the region, which will be dealt with when the graphs are constructed. Restricting paths from entering regions that have been entered at a higher level of the tree does not result in loss of any minimal paths, since all possible exits from that region have already been explored at the higher level; repeating those paths further down the tree only leads to longer paths with more crossings. Distance Tree region restriction can thus be defined as follows:

\begin{definition}\label{def:dtrr}
Given a Distance Tree as described, a \textbf{Distance Tree Region Restriction} states that once one complete level of a Distance Tree is constructed, no region on that level may be visited by any branch of the Distance Tree at any later level.
\end{definition}
which then leads us to:

\begin{theorem}\label{thm:dtrres}
In generating a Distance Tree for minimal Kn from minimal Kn-1 as described, the use of Distance Tree Region Restriction does not eliminate any possible minimal graphs from being generated.
\end{theorem}

The minimal crossing number for this graph is calculated starting with $\nu$(K$_{n-1}$), which is passed to the program as a parameter. Each time a path is completed through the tree and traced back for transfer to the Path List, the number of levels is counted and cumulatively added to the starting crossing number (for $n$ - 1), since each level represents one crossing. When all paths have been created, $\nu$(K$_{n}$) is the cumulative result. Note that with respect to crossing number, it doesn't matter how many times a vertex is found on a given level; each vertex only has a path to it counted once, and after being removed from the edges-to-add list, will never be sought at a lower level. 
}%\end subsection{Distance Tree}

\subsection{Path List}\label{sec:pl}
{
As mentioned, a Path List is composed of PathNodes, which are created based on corresponding TreeNodes as the path is traced from leaf to root. The Path List is actually a list of lists, where each individual sublist represents one path from the new vertex to an original native vertex.
 
A PathNode class object consists of three data members: the edge crossed by this segment of the path, the region crossed by this segment of the path, and the terminal vertex, if any, found in this region. All PathNodes in a single path will have a terminal vertex of 0 except the last one. When linked together into a sublist, this provides the entire path for the edge from the new vertex $n$ to an original vertex $i$.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/K5PathList.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A K$_5$ Graph with Completed Path List}
       \label{fig:K5PL}
 \end{figure}

When complete, the Path List contains all of the sublists for all of the paths from $n$ to $i$ (Figure~\ref{fig:K5PL}). Prior to saving them to a file, the sublists are sorted so that all the paths to a single vertex, $i$, are listed together, and the sublists proceed from $i = 1$ to $i = n-1$.
}%\end subsection{Path List} 

\subsection{K$_n$ Graph}\label{sec:kng}
{
A K$_n$ Graph is not a unique data structure, but simply an instance of a Region List. It is created by starting with the input K$_{n-1}$ Region List and inserting a set of new paths from the Path List, one for each original vertex. The appearance of the new paths radiating out from the newly added vertex to various points of the graph in a star configuration is what led to the Star Analysis moniker (Figure~\ref{fig:star}).
\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/star.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_7$ Path Overlays on Minimal K$_6$ Demonstrating Star Configuration}
       \label{fig:star}
 \end{figure}
Graphs can be built from all combinations of minimal paths or from some other subset of the Path List.

Paths are added one by one in the reverse order from which they were created, starting from the terminal vertex and proceeding back to the newly inserted vertex. Edge segments are laid down sequentially in the order they occur in the Path List, with the graph regions updated after each addition. Each update requires that the crossed region be split into two new regions by the newly laid segment, and the graph is amended to reflect this. Since these region updates create a partial graph that may not match the Path List of paths that are added subsequently, two look-up tables are maintained to associate old edges and old regions with new ones.
 
When one path from each of the $n - 1$ vertices to the $nth$ has been added, the resulting graph depicts K$_n$ with crossing vertices still in place to keep it planar. For purposes of drawing the actual K$_n$ Graph, the crossing vertex numbers are removed. Completed graphs are saved to a file for further processing into isomorphic families.
 
We mentioned earlier one potential problem that can arise when paths are laid down totally independent of one another. That is the situation where two independent edges enter a region and make an illegal crossing midregion before exiting in different directions (Figure~\ref{fig:conflict}).

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.0in]{ch3/conflict.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Demonstration of a Conflict Between Two Independently Constructed Paths}
       \label{fig:conflict}
 \end{figure}
The region and edge look-up tables prevent these graphs from being created, as seen in the following example. When edge ($4,7$) is created (Figure~\ref{fig:conflictrepair}, solid line), the graph's Region List is updated to reflect new regions R7, R8, and R9. The region look-up table adds R7 as a subset of R2, R8 as a subset of R4 and R9 as a subset of R6. Similarly, the edge look-up table adds the entries shown to keep track of the new legal subsets of edges that were crossed. When the program attempts to lay down edge ($5,7$) by the second path (Figure~\ref{fig:conflictrepair}, dashed line), it encounters edge (12,11), which is not a legal subset of the expected edge in its PathNode, (3,8). Therefore, the graph is thrown out as an illegal graph. The other alternative path from $5$ to $7$ (Figure~\ref{fig:conflictrepair}, dash-dot line), is legal because it finds edge (11,6) as a subset of (8,6) and edge (1,10) as a subset of (1,8). For the purpose of defining an edge, the order in which the vertices are specified is not critical. In this example, the legal edge passes through regions whose names designations have not changed, so the region look-up table is not needed. 

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/conflictrepair.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Resolution of Path Conflict}
       \label{fig:conflictrepair}
 \end{figure} 
}%\end subsection{K$_N$ Graph}
}%\end section{Data Structures}

\section{Example: K$_6$ to K$_7$}\label{sec:exk6k7}
{
We will now step through the process of building a K$_7$ graph from a minimal K$_6$ to illustrate the entire algorithm. We begin with an instance of a minimal K$_6$ graph with a new vertex 7 inserted into region R9 (Figure~\ref{fig:examplestart}). This graph, encoded as a Region List, is passed to the Star Analysis program, along with an edges-to-add list, and the identity of the region where the new vertex should be placed, R9. The root TreeNode, Level 0, is created as shown in Figure~\ref{fig:examplestart}, with values of (0,0) for the edge variable, since no edge was crossed; 9 for the region; 0 for the vertex initially; and the pointers.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/examplestart.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Starting to Grow K$_7$ From K$_6$, With Vertex 7 Placed and Edges-to-Add List}
       \label{fig:examplestart}
 \end{figure} 
 
The first step is to connect any vertices on the edges-to-add list that exist in the current region. Scanning the edges-to-add list, we find 3. The vertex value in the TreeNode is updated to 3. A PathNode is created and added to the Path List, as a path of one step, containing the following values (copied from the TreeNode): (0, 0) for edge, 9 for region, and 3 for vertex (See Figure~\ref{fig:expath}). The TreeNode vertex value is returned to 0, and we resume scanning the edges-to-add list, where we find 6. The process of creating a PathNode is repeated, and it is added to the PathList. No further vertices are found on the edges-to-add list, so we remove edges 3 and 6, and then allocate memory for TreeNodes at the next level, Level 1 (Figure~\ref{fig:excont}). We are done with this level, so we place R9 on the restricted region list.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/excont.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Continuing to Grow K$_7$ From K$_6$}
       \label{fig:excont}
 \end{figure} 
 
Region R9 has three edges on its boundary. Since there are no regions other than R9 on the restricted region list, we create nodes that cross each of these edges. The nodes are seen on Level 1 of Figure~\ref{fig:excont}, with data values assigned.  We inspect the remaining edges-to-add for any that can be added directly in any of the three regions. We find vertex 2 in R12 first, and update the vertex value to 2 in our TreeNode. We create a new path on the Path List, consisting of two PathNodes as shown in Figure~\ref{fig:expath} by tracing backwards using the parent pointer. Moving on across the level, we find vertex 5 in R11. Another path is created. No further paths can be completed on this level, so we remove 5 and 2 from our edges-to-add list and add regions R11, R12, and R13 to the restricted regions list. 

The next level of nodes, Level 2, is created, shown in Figure~\ref{fig:exdone}. For clarity, only TreeNodes that result in vertex connections are shown. Since all remaining vertices are connected on this level, none of the TreeNodes not shown here lead on further down the tree.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/exdone.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Completed Distance Tree for Vertex Placement in Region 9}
       \label{fig:exdone}
 \end{figure} 
Scanning across the row, we see that vertices 1 and 4 are both encountered on this level via two different paths each. PathNodes are created and the paths are traced back for all four of these terminations. At the end of the level, edges 1 and 4 are removed from the edges-to-add list, which is now empty. The final step is to sort the Path List so that the vertices are in order, shown in Figure~\ref{fig:expath}, and save the Path List to a file.

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=7.0in]{ch3/expath.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Completed Path List for New Vertex Placement in Region 9}
       \label{fig:expath}
 \end{figure} 

After all the input graphs have been evaluated, one for each region assignment of the new vertex from each isofamily, and all the Path Lists have been saved, we can begin to build graphs. Let's assume we have reopened the Path List generated above, along with the starting K$_6$ graph from Figure~\ref{fig:examplestart}. Our first graph will be created by selecting one edge for each terminating vertex, in this case the first, third, fourth, fifth, seventh and eighth paths. The program is currently written to cycle through all combinations of shortest paths to create a graph for each combination, but for this example, one will suffice. Each edge back to vertex 7 is created, segment by segment. After each addition, the Region List representing the Graph is updated to reflect the new region boundaries, and the look-up tables are updated to reflect the region and edge divisions. When all edges have been added, the Region List/Graph looks like Figure~\ref{fig:endK7}. The crossing vertices are left numbered to keep the graph planar and provide region boundaries. It is again saved, to be sent onwards to $NAUTY$ for isomorphic family assignment. 

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.0in]{ch3/endK7.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Completed K$_7$ Graph With Crossing Vertices Labeled}
       \label{fig:endK7}
 \end{figure} 
}%\end section{Example: K$_6$ to K$_7$}
\newpage