\chapter{Progression toward an Effective Algorithm}\label{chap3}
 
  Work in the direction of growing minimal K$_{n}$ from minimal K$_{n-1}$ starts
  with the exhaustive search algorithm, presented in Section~\ref{sec:es}, modified 
  such that the root of the search tree is
  minimal K$_{n-1}$.  Guy~\cite{Guy72:cng} states that if Conjecture~\ref{cj:Kn} is
  true, then it is false to conjecture that a 
  minimal K$_{n}$ always contains
  a minimal K$_{n-1}$ for $n$ odd and $n\ge9$.  If Conjecture~\ref{cj:Kn} 
  is true, it can be demonstrated that minimal K$_{n}$ always contains a minimal
  K$_{n-1}$ for $n$ even, but no demonstration is available for $n$ odd, specifically for 
  $n=9$ and probably for larger odd $n$.  A formal proof showing minimal K$_{n}$ does
  not contain minimal K$_{n-1}$ for $n$ odd has not been found in the literature
  nor has an example of a minimal K$_{9}$ that does not contain a minimal K$_{8}$ been
  located.  In personal correspondence, Guy indicated that at one time there
  was a census of the minimal drawings of K$_{9}$.  In the attempt to recover these
  graphs for evaluation it was learned that they have been lost over the years.  It is also
  noted that the definition of isomorphism used for the missing census of minimal K$_{9}$
  is different from the one employed for this body of work. These differences and the fact
  that Conjecture~\ref{cj:Kn} is a conjecture leaves the door open for the exploration
  presented.  
  
  Although no example of a minimal K$_{9}$ that does not 
  contain minimal K$_{8}$ has presented itself at this time,
  it is evident {\it via} mathematical evaluation that the
  possibility that such a drawing may theoretically exist cannot be disregarded.  
  It is easily verified that removal of
  any vertex from minimal K$_{9}$ does not always produce a minimal K$_{8}$; however, this does
  not show irrefutably that minimal K$_{9}$ does not contain a minimal K$_{8}$.  
  Figure~\ref{fig:K9} illustrates a minimal K$_{9}$ having
  both minimal and non-minimal K$_{8}$ subgraphs.  Figure~\ref{fig:K8Subs}(a) shows a minimal K$_{8}$ subgraph
  with 18 crossings, and Figure~\ref{fig:K8Subs}(b) shows a non-minimal K$_{8}$ subgraph with 22 crossings.
  
 \begin{figure}[!ht]
       \begin{center}
        \includegraphics[width=4.0in]{ch3/K9Chap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Minimal K$_{9}$ with Minimal and Non-minimal K$_{8}$ Subgraphs}
       \label{fig:K9}
 \end{figure}
    
 \begin{figure}[!ht]
       \begin{center}
        \includegraphics[width=4.0in]{ch3/K8SubsChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Minimal and Non-minimal K$_{8}$ Subgraphs of Minimal K$_{9}$}
       \label{fig:K8Subs}
 \end{figure}
  Recall that the responsibility of a vertex
  is defined by Guy~\cite{Guy72:cng} as the total number of crossings on all edges incident 
  to that vertex.  Given that each crossing is the responsibility of four vertices, the total
  responsibility of a graph is $4c$, where $c$ is the number of crossings.  Start by considering
  a minimal K$_{7}$.  A drawing of minimal K$_{7}$ contains a vertex with responsibility at
  least $\left\lceil\frac{4c}{7}\right\rceil = 6$.  This is the average responsibility of all 
  vertices in the
  graph.  Removal of this vertex and all edges incident to it leaves a drawing of K$_{6}$ with
  at most $c-\left\lceil\frac{4c}{7}\right\rceil = \left\lfloor\frac{3c}{7}\right\rfloor = 3$
  crossings.  All vertices of minimal K$_{7}$ must have responsibility $6$.  If there existed one
  with larger responsibility, its removal would leave a K$_{6}$ with fewer than 3 crossings which is
  not possible.  Thus removal of any vertex from
  minimal K$_{7}$ will leave a minimal K$_{6}$.  A similar argument exists regarding minimal
  K$_{8}$ containing minimal K$_{7}$ subgraphs.  
  
  In the case of minimal K$_{9}$ with K$_{8}$ subgraphs, we 
  would get a similar result if minimal K$_{9}$ contained 34 crossings, but it does not.  
  Minimal K$_{9}$ has 36 crossings and by the responsibility argument, the average responsibility
  of its nine vertices is 16.  Removal of a vertex with responsibility 16 will leave a K$_{8}$ with
  20 crossings, which is nonminimal.  Thus removal of any vertex from a minimal K$_{9}$ does not
  guarantee a minimal K$_{8}$ subgraph.  Keep in mind that the vertex removed has the average
  responsibility of all vertices in the minimal K$_{9}$.  Given that minimal K$_{8}$ has 18
  crossings, it may be the case that all minimal K$_{9}$ have at least one vertex with responsibility
  18.  Removal of this one vertex would result in a minimal K$_{8}$ subgraph.    
  
  The question becomes: does there exist a minimal K$_{9}$ such that each of its nine
  K$_{8}$ subgraphs is not minimal?  Specifically, the question is posed: does
  there exist a K$_{8}$ with 19 crossings that can generate a minimal K$_{9}$ with a
  maximum vertex responsibility of 17?  All vertices of this minimal K$_{9}$ cannot have 
  responsibility 16, or minimal K$_{9}$ would have 34 crossings, and removal of any vertex
  would result in nonminimal K$_{8}$ with 20 crossings.  There would have to be at least 1 
  vertex with responsibility of 17.  Removal of this vertex would result in a K$_{8}$
  with 19 crossings.  This would have to be the maximum responsibility since if a vertex
  with responsibility 18 existed in the graph, its removal would present a minimal K$_{8}$
  subgraph and, of course, responsibility larger than 18 cannot exist or the crossings in
  minimal K$_{8}$ would be fewer than the 18 crossings of minimal K$_{8}$.  Until
  this question is answered, it is not confirmed whether every minimal K$_{9}$ contains
  a minimal K$_{8}$ or not.  It is the case for all $n < 9$ that removal of any vertex 
  from minimal K$_{n}$ does leave a minimal K$_{n-1}$ subgraph.  
  
  Given the possibility that not every minimal K$_{9}$ can be derived from minimal K$_{8}$, and
  that no proof to the contrary has presented itself,
  it is agreed, at this point, that some minimal K$_{n}$ may be lost,
  specifically those created from nonminimal K$_{n-1}$,
  for $n$ odd and $n\ge9$ by using minimal K$_{n-1}$ as the root of the search tree.  
  It is assumed, for now, that it is possible that branches are 
  pruned off the search tree that do not step through a minimal 
  K$_{n-1}$ on a path leading to minimal K$_{n}$.  Refer to Chapter~\ref{chap5} for future 
  work to further explore this topic.  Given this concession, from this point forward, 
  the discussion is based on using minimal K$_{n-1}$ as the root graph of the search tree.
  
  This chapter presents the new ideas that mold the exhaustive search
  algorithm, outlined in Section~\ref{sec:es}, into the foundation for an effective algorithm that
  can be used in growing minimal K$_{n}$ from minimal K$_{n-1}$.  Section~\ref{sec:apii} 
  addresses parallel load balancing issues in the Tadjiev and 
  Harris~\cite{Tadj98:pcgvmcng,th97:pcmcng} implementation.  An overview of the new parallel 
  implementation developed is presented in Section~\ref{sec:pio}
  for clear understanding of the three new search space reductions using
  this parallel scheme that are addressed in Section~\ref{sec:ssr}. 
  The chapter concludes with a new technique, Star Analysis, discussed in Section~\ref{sec:dtpl}
  that steps away from the job-based parallel implementation of Section~\ref{sec:pio}. 
  
\section{Parallel Load Balancing}\label{sec:apii}

 In the initial parallel implementation of the exhaustive search algorithm overviewed in
 Section~\ref{sec:es}, Tadjiev and Harris~\cite{Tadj98:pcgvmcng,th97:pcmcng} implemented
 a basic static partitioning of the search tree across the processors used.
 Static partitioning is most beneficial when the problems being addressed have
 data sets that are completely defined prior to run-time and that are often divided among 
 the processors, each computing its own results from its individual data set.  A drawback
 of static partitioning is that when one processor finishes working it must wait idly while 
 the other processors complete their task.  The work load is not evenly distributed across
 the processors.  There is unrealized concurrent execution of the
 data in this case~\cite{ymfh:agqs}.  Tadjiev and Harris note this problem with the 
 initial implementation they produced.  Figure~\ref{fig:ul}
 illustrates one way an unbalanced search tree may be allocated to processors.  Processors
 P2 and P3 will finish their allocated load and sit idle while P1 processes its
 larger load without the ability to share it.
 
 \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=3.5in]{ch3/UnbalancedChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Unbalanced Work Load}
       \label{fig:ul}
 \end{figure}
 
 One solution to the unbalanced load problem is dynamic load
 balancing.  A work queue is one method of implementing dynamic load balancing and thereby ensuring
 a work load that is evenly distributed across many processors.  This balancing can be 
 centralized, residing with a master process, or decentralized, controlled by each slave, or
 a unified system that may be used combines the two .  The work queue is especially useful 
 in load balancing when dealing with irregular data structures such as unbalanced search trees.
 
 In centralized load balancing, the tasks to be performed are held by the master and distributed
 to the slaves as they finish other tasks and become idle.  Efficiency is maximized as slave idle
 time is minimized.  One disadvantage of centralized load balancing is the possibility of a master
 task distribution bottleneck.  A bottleneck occurs when many slaves request tasks simultaneously
 but the master can issue only one task at a time.  In decentralized load balancing, local
 processors keep their own work pools.  This strategy has the benefit of avoiding a master task
 distribution bottleneck.  Decentralized load balancing is similar to static partitioning in its 
 apparent problems.  In a unified system, the slaves may request work from each 
 other or from a centralized master queue.
 
 To alleviate the balancing problems noted by Tadjiev and Harris, a dynamic queuing system was
 created with a unified system employing both a master queue and individual slave queues.  The
 slaves request work from a central queue and also maintain their own individual queue.  The
 implementation, illustrated in Figure~\ref{fig:pwg}, has the master creating the first $m$ jobs 
 and placing them on the central queue (managed by the master).  The master then sends one job
 to each slave processor.  Each processor will create more jobs while processing.  These jobs
 are kept in a local work queue managed by each individual slave.  When a slave's local work
 queue reaches a user-defined limit indicating a large queue size, it sends the extra
 jobs to the master for placement in the central queue.  If a slave depletes its local queue, it
 requests a new job from the master to supply its queue again so it may
 continue processing.  If the master queue is empty and a slave requests a job to process, the
 master will request jobs from the other working slaves.  The entire process terminates when all
 slaves are idle and the central queue is empty.  Refer 
 to~\cite{Mart03:pqscipmlbc},~\cite{Yuan2004:gqstsrrccnkn}, and~\cite{ymfh:agqs} 
 for more details on this unified queuing system implementation.
 
 \begin{figure}[!ht]
       \begin{center}

         \includegraphics[width=4.0in]{ch3/WorkQueueChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Parallel Work Queue}
       \label{fig:pwg}
 \end{figure}
 
 

\section{Parallel Implementation Overview}\label{sec:pio}
 
 As stated at the beginning of Chapter~\ref{chap3}, a minimal K$_{n-1}$ is the root of
 each search tree examined in the search for minimal K$_{n}$.  A brief overview of how 
 the parallel implementation works is
 presented now to facilitate clarity of the remaining sections of this chapter.
 
 Figure~\ref{fig:mrst} illustrates a minimal K$_{6}$ graph at the root of the search tree
 to be examined in a branch-and-bound depth-first search method in pursuit of minimal K$_{7}$.
 For this discussion, the terminology {\it native vertex} is introduced to represent 
 a true vertex of a graph, not a crossing.  
 A crossing vertex is introduced to planarize the graph each time an edge segment is placed unless
 it is to a native vertex on the boundary of a current region.  An edge segment will terminate
 at a native vertex only if the vertex is the destination of the original edge.
 Crossing vertices
 are indexed starting one greater than the native vertex, indexed $n$, being added to the graph.  In 
 Figure~\ref{fig:mrst} the native vertices of the graph K$_{6}$ are numbered 1 through 6,
 while the crossing vertices are numbered 8, 9 and 10.  The index 7 is reserved for the new vertex being
 placed into the graph to generate K$_{7}$.  A preprocessing step adds any direct 
 connections from the new vertex $n$ to any native vertices on the boundary of the region in which  
 the new vertex is placed.  Each region of the root graph is used as a possible location
 for the new vertex placement.  Notice in Figure~\ref{fig:mrst} that because vertex 7 was 
 randomly placed in the region defined by vertices 2 and 4 and cross vertex 10, the 
 edges (7,2) and (7,4) do not appear in the list of edges to add.
  
  \begin{figure}[!ht]
       \begin{center}
          \includegraphics[width=3.0in]{ch3/K6Chap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Minimal K$_{6}$ Prepared as the Root of the Search Tree}
       \label{fig:mrst}
 \end{figure}
  In generating minimal K$_{n}$, there is more than one minimal K$_{n-1}$ 
 root graph for $n \ge 7$.  Refer to Chapter~\ref{chap4} for more details on how these root
 graphs are derived.  
 
 The parallel implementation makes use of one master (the manager) and
 several slave processors.  When initiated, the program reads in
 each of the minimal K$_{n-1}$ root graphs along with the edges that need to be added to each
 graph to generate K$_{n}$ and begins the process by laying down one edge segment to each nonadjacent
 edge through each 
 possible initial region for each new graph construction.  Each edge segment laid down creates a 
 new graph with a modified list of edges
 to add (less the newly laid down edge segment). Figure~\ref{fig:firstedge} illustrates 
 the result of this process as applied to the K$_{6}$ in Figure~\ref{fig:mrst}, given that vertex $7$ is
 placed in the region shown.  Three possible segments can be laid down from vertex 7, thus three
 graphs are constructed.  The edge segment laid down introduces a new crossing to the graph, cross vertex
 11.
 
  \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=6.0in]{ch3/FirstEdgeChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Stepping toward K$_{7}$ from Minimal K$_{6}$}
       \label{fig:firstedge}
 \end{figure}
 
 The new
 graph, with its updated list of edges to add, is enqueued as a job in the master queue.  Each slave 
 processor requests an initial job, and the master sends a 
 job to each requesting
 slave.  As the slaves create new jobs, they add them to their local queues.  
 The master monitors requests from the slaves for more work and transfers jobs 
 from slaves that have jobs enqueued locally to those in need of jobs to process.  
   
 Each graph in any job is treated as planar. As mentioned, a crossing vertex is introduced 
 to planarize a graph after each edge segment is placed.  If the number of
 crossing vertices exceeds the current minimum number of crossings found from previously examined 
 graphs or Guy's conjectured solution, Conjecture~\ref{th:Kn}, then the job is disposed of.  
 Otherwise it is packaged, with the 
 updated list of edges to add, as a new job and enqueued, and the 
 search algorithm is employed again with this planar graph as the root of its own subtree. 
  
 When the list of edges to add is empty, minimal K$_{n}$ has been constructed.  The crossing vertices
 are eliminated, and crossings are reintroduced in their place.  Figure~\ref{fig:cvtocross} illustrates
 this process. The graph at the center top is minimal K$_{5}$ with the following preparatory additions: 
 the one crossing is replaced with crossing vertex $7$, vertex 6 is placed in one region, 
 and direct connections are made to vertices $1$, $2$ and $5$.  The remaining edges
 to add are (6,3) and (6,4).  Two new crossings are introduced while generating
 minimal K$_{6}$ and are labeled as crossing vertices 8 and 9, as illustrated in the lower left figure.  
 The image in the lower right is the final minimal
 K$_{6}$ with the crossing vertices removed and replaced with crossings. The final product is 
 a minimal K$_{6}$ with 3 crossings.
  
  \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.0in]{ch3/cvtocrossChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_{6}$ Constructed from K$_{5}$ with 1 Crossing Vertex}
       \label{fig:cvtocross}
 \end{figure}
 
\section{Search Space Reduction}\label{sec:ssr}
 A unified queuing system, as discussed in Section~\ref{sec:apii}, was incorporated into a parallel 
 implementation of the exhaustive search algorithm of Section~\ref{sec:pio}.  
 Exhaustive search algorithms are
 not efficient, and the search trees built become huge quickly.  Lengthy runtime problems
 arise
 while creating complete graphs of order $8$.  Techniques for search space reduction
 are critical in achieving solutions for larger $n$.  Three
 search space reduction techniques applied to the unified queuing parallel implementation
 are presented in Sections~\ref{sec:oep} through~\ref{sec:rrr}. 

\subsection{Order of Edge Placement}\label{sec:oep}

Given that the initial graph used in generating K$_{n}$ is a complete graph of order $n-1$, 
the process of generating
K$_{n}$ is essentially that of placing a star graph K$_{1,n-1}$ centered at vertex $n$ upon K$_{n-1}$ with
vertex $n$ in a region of K$_{n-1}$.  This leads to the following theorem.

\begin{theorem}\label{thm:order}
	In the process of generating graph descriptions of K$_{n}$ from K$_{n-1}$, 
	it does not matter in which order the edges incident to a 
	new vertex n are laid down.
	
	\smallskip \noindent {\bf Proof:}
	{\sl Let $G$ be a minimal K$_{n-1}$.  Let $n$ be the vertex being placed
	into any one region of $G$.  To create K$_{n}$, $n-1$ edges must be placed, each one
	connecting
	$n$ to one of the $n-1$ vertices of K$_{n-1}$.  All $n-1$ edges being added
	to $G$ are adjacent edges since they are all incident with vertex $n$.  By  the definition 
	of a good graph these edges cannot cross each other or meet at any point other
	than vertex $n$.  Thus each edge is independent of every other. The placement of
	any one does not affect the placement of any other.  Therefore, the order
	in which the edges are placed does not matter.	\hfill $\bowtie$}
	%
\end{theorem}

The ability to disregard order of edge placement leads to a significant computational
savings as compared to having to examine all permutations of edge placement.
  
\subsection{Region Restriction}\label{sec:rr}

In generating graph descriptions for minimal K$_{n}$, the unified queue parallel 
implementation that adheres to the definition of a good drawing is inefficient 
because an edge path may visit an unnecessary region or 
return to an already visited region of the graph, sometimes repeatedly.  This 
observation leads to the next search space reduction: Region Restriction.

Figure~\ref{fig:gdpe} illustrates four of many possibilities of a $u$-$v$ path
with the first edge segment crossing
through region R1.  Each of the drawings is a good drawing based on 
Definition~\ref{def:good drawing}.  R1 has five edges, three of which are legal for $uv$ to cross.
Recall that each edge adjacent to R1 and not incident to vertex $u$ will be used in 
generating all valid $uv$ paths, so it is assured that all edge placements shown in
Figure~\ref{fig:gdpe} will be generated.  Figures~\ref{fig:gdpe}(a) and (b) both
illustrate placement of edge $uv$ with one crossing, and Figures~\ref{fig:gdpe}(c) and (d)
have two and four crossings, respectively.  Note that the new edge in both (c) and (d) exits
R1 on the same edge and enters R3 on the same edge, but the edge in Figure~\ref{fig:gdpe}(d)
travels less efficiently by entering R4 twice, creating more crossings than the drawing shown in (c).  
Thus the drawing in 
Figure~\ref{fig:gdpe}(d), though a good drawing, will not aid in producing a complete graph
with a minimum number of crossings because the drawing in (c) has fewer crossings.  This
observation leads to Lemma~\ref{lm:noback}.

\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.0in]{ch3/gdpeChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Good Drawings for Placement of Edge $uv$}
       \label{fig:gdpe}
 \end{figure}

	\begin{lemma}\label{lm:noback}
	Given a simple connected graph G with nonadjacent vertices u and v and at least two regions,
	restricting the edge
	$uv$ from reentry into an already visited region of G does not eliminate
	any possible minimal graphs from being generated.
	
	\smallskip \noindent {\bf Proof:}
	{\sl Let R be a region of graph G on whose boundary $u$ lies.  By definition of a region,
	exactly two edges of R are adjacent to $u$, and any region of G has at least three edges.
	When applying the rules for a good drawing, at least three non-adjacent edges (nae) are needed to exit, enter,
	and reenter a region.  Thus, we need only consider regions with five or more edges.
	
	Examining the case of the $u$-$v$ path exiting, reenter, and reexiting R, let
	$f: u = u_{0}, i_{1}, p_{1}, e_{1}, ... e_{j}, p_{2}, i_{2}, p_{3}, e_{m} ... e_{n} = v$
	represent the $u$-$v$ path where:
	\begin{itemize}
		\item $p_{1}$ is the cross vertex created as the path exits R,
		\item $p_{2}$ is the cross vertex created as the path reenters R,
		\item $p_{3}$ is the cross vertex created as the path reexits R,
		\item $i_{1}$ and $i_{2}$ are the edges of the path internal to R,
		\item and $e_{1}, ... e_{j}$ and $e_{m},...e_{n}$ are the portions of the path external to R.
	\end{itemize}
	The subpath $i_{1}, p_{1}, e_{1},...e_{j}, p_{2}, i_{2}, p_{3}$ can be replaced with a single
	edge, $i_{3}$, thus shortening the path and reducing the number of crossings by at least two
	(represented by cross vertices $p_{1}$ and $p_{2}$).  Figure~\ref{fig:lem1} illustrates this 
	substitution.  Thus, restricting region reentry will eliminate only those graphs with 
	nonminimal crossings.
	
	The argument is the same for any region of G, (not just those on whose boundary $u$ lies), 
	encountered on the $u$-$v$ path as well as for more reentries and reexits of any particular
	region. 
	
	\hfill $\bowtie$}
	%
	\end{lemma}
	
\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.5in]{ch3/Lem1Chap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Subpath Replacement}
       \label{fig:lem1}
 \end{figure}
 
	A second observation is illustrated in Figure~\ref{fig:badnbr}.  It 
	illustrates two $u$-$v$ paths in graph $G$, both of which
	visit region R2.  Figure~\ref{fig:badnbr}
	(b) generates more crossings than (a) in its path through region R2.  

	\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.0in]{ch3/badnbrChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Two Possible Paths for Laying down Edge $uv$}
       \label{fig:badnbr}
 \end{figure}	
	Figure~\ref{fig:iesegs} shows the laying down of the six possible initial edge segments at the
	start of the $uv$ path.  After laying down the initial edge segment, any other edge segments on the
	$uv$ path are restricted from entering regions R1, R2, and R3.
	With each additional
	edge segment placed, the relevant regions will join the list of restricted regions for 
	any given edge.
	
	\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=3.0in]{ch3/iesegsChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Initial Edge Segments from Vertex $u$ to Other Nonadjacent Vertices}
       \label{fig:iesegs}
 \end{figure}
	
	For the following lemma, define a {\it neighboring region} to be any region which shares a 
	common edge with the region of focus.
	
		\begin{lemma}\label{lm:nonbr}
	Given a simple connected graph G with nonadjacent vertices u and v and at least two regions,
	restricting the edge $uv$ from entering the neighboring regions of a region 
	it crosses does not eliminate	any possible minimal graphs from being generated.
	
	\smallskip \noindent {\bf Proof:}
	{\sl Let R$_{1}$, ..., R$_{i}$ be the regions of G on whose boundaries lie vertex $u$.
	We consider only the case in which vertex $v$ does not lie on the boundary of R$_{1}$,
	..., R$_{i}$ (otherwise an edge with no crossings could connect $u$ and $v$).
	Let $p_{n}$ be the last vertex in the $u$-$v$ path that lies on the boundary of one of
	R$_{1}$, R$_{2}$, ..., R$_{i}$.  That is, the $u$-$v$ path can be written
	$f: u = u_{0}, e_{1}, p_{1}, e_{2}, p_{2}, ... e_{n}, p_{n}, ... v$ where $p_{1}, p_{2}, ...
	p_{n}$ are all cross vertices created by the $u$-$v$ path.
	The segment of the path from $u$ to $p_{n}$ can be replaced with one edge thus shortening
	the path and removing the crossings represented by $p_{1}, p_{2}, ...p_{n}$.  Thus, restricting
	an edge path from entering neighboring regions of a region it crosses eliminates only
	nonminimal graphs.
	\hfill $\bowtie$}
	%
	\end{lemma}
	
	These two lemmas lead us to a new definition that places a tighter bound on the definition
	of a good drawing of a graph.
	
	\begin{definition}\label{def:rrgd}
 Let \[f:u=u_{0},e_{1},u_{1},e_{2}...,u_{k-1},e_{k},u_{k}=v\] denote the u-v path laid down in
 graph $G$ where $e_{i}$ is an edge segment through one
 region of G.  Let $H$ = $G$ + $f$.  
 The graph H is a \textbf{region restricted good graph} if every region of $H$ has 
 at most two vertices of $f$ on its boundary. 
 \end{definition}

	Definition~\ref{def:rrgd} in conjunction with Lemmas~\ref{lm:noback} and~\ref{lm:nonbr} allows
	for the statement of the following theorem.
	
\begin{theorem}\label{thm:rr}
	Employing the definition of a region restricted good drawing of a graph while creating
	minimal K$_{n}$ from minimal K$_{n-1}$ does not eliminate any possible minimal graphs from
	being generated.
\end{theorem}

	Modification to the graph generation algorithm in order to apply Region Restriction
	is minimal.  Whenever an edge segment is laid
	down, its initiating vertex is used to add to, or create, a list of restricted regions for that edge.
	Region Restriction performed well when generating K$_{8}$, yet encountered runtime difficulties when 
	generating K$_{9}$. 
	
	Table~\ref{tab:RRresults} shows a comparison of the number of partial edges laid down when
	building K$_{n}$ for $5 \le n \le 8$ with and without Region Restriction.  Results in this
	table were generated running on six parallel processors.  For all $n$ in the table, 
	Region Restriction generated the same graphs with the minimum number of crossings as
	the non-restricted test results.

	\begin{table}[ht]
	\begin{center}
	\begin{tabular}{|c|r|r|r|}\hline
	{\bf Vertices} & {\bf $\nu(K_{n})$}	& {\bf Good Graph} & \multicolumn{1}{c|}{{\bf Restricted}} \\
	{\bf ($n$)}	&		&	& {\bf Good Graph} \\ \hline
	5	& 1		& 3		& 3 \\ \hline
	6 	& 3 		& 203 		& 71 \\ \hline
	7 	&9 		& 1,498,775 	& 19,979 \\ \hline
	8	& 18		& *		& 46,697,854 \\ \hline
	\end{tabular}
	\end{center}
	\caption{Region Restricted {\it versus} Good Graph Jobs Processed}
	\label{tab:RRresults}
	\end{table}	
	   
	A substantial search space reduction resulted, as can be seen by comparing results for $n=7$.  
	The search space is reduced by a factor of nearly 75.  Running without Region Restriction,
	K$_{8}$ results were not achieved in over a week of runtime.  With Region Restriction, all
	jobs were fully processed in under four hours.  This time reduced to just over two hours
	when eight processors were employed.  
	
	Figure~\ref{fig:RRk8Xprocs} illustrates 
	execution time using Region Restriction to run K$_{8}$ on six to sixteen processors.

	\begin{figure}[!ht]
       \begin{center}
       	\includegraphics[width=4.5in]{ch3/RRk8Xprocs.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Region Restriction Execution Time for K$_{8}$ on $P$ Processors}
       \label{fig:RRk8Xprocs}
 \end{figure}	
	 
  An attempt to generate minimal K$_{9}$ using Region Restriction was not successful given a 
	runtime of one week on sixteen processors.  This indicated that tighter restrictions on the search
	space were necessary.  More pruning was imperative.  


\subsection{Radical Region Restriction}\label{sec:rrr}

Radical region restriction is a greedy edge placement based on the analysis of the
number of regions between vertices.  When laying down all edges from vertex $u$ to
vertex $v$ of graph $G$, only those edges that are of the minimum region separation from
$u$ to $v$ are generated.  For example, Figure~\ref{fig:edgePlacement} shows four of the
ten possible $uv$ edge placements for the given graph.  Figure~\ref{fig:edgePlacement}(a) and
(b) are the only two possible $uv$ edge placements that have the minimum number of regions
(in this case two) separating $u$ and $v$.  The minimum number of separating regions,
being two, indicates that only one crossing will be generated in each of these cases.  
Figure~\ref{fig:edgePlacement}(c) and (d) show two other $uv$ edge placements of the remaining eight,
each of which separates $u$ and $v$ by three regions.  A three region separation will
introduce two crossings. 

\begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=5.0in]{ch3/PlaceUVChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Placement of Edge $uv$}
       \label{fig:edgePlacement}
 \end{figure}
 
 Radical Region Restriction determines, for each of the $n-1$ edges that need to
 be laid down on the given K$_{n-1}$ graph the minimal number
 of regions that need to be crossed to lay down the complete edge.  It then proceeds
 to follow all branches of the search tree that do not exceed this minimal number of
 region crossings for each edge needing to be laid down.  This assures that all edges
 of minimum length are generated.  
 
 \begin{theorem}\label{th:rrr}
 	In generating minimal K$_{n}$ from minimal K$_{n-1}$, the use of Radical Region Restriction
	does not eliminate any possible minimal graphs from being generated.
		
		\smallskip \noindent {\bf Proof:}
	{\sl Radical Region Restriction dictates that all edges from vertex $u$ to vertex $v$ be
	the shortest length possible with the length of an edge determined by the number of regions
	crossed by the edge $uv$.  Assume minimal K$_{n}$ exists with $f:$ a $u$-$v$ path from $u$ to
	$v$ with nonminimal length.  It is known from Theorem~\ref{thm:order} that no two edges
	from new vertex $n$ to any vertex $n-i$, $1 \le i \le n-1$, interfere with each other, so
	the nonminimal length of path $f$ is not due to placement of the other $n-1$ edges.
	Path $f$ will add at least one more crossing to K$_{n}$ than
	a graph constructed with a $uv$ edge of minimal length.  Thus a contradiction arises and path
	$f$ cannot exist in minimal K$_{n}$. 
		\hfill $\bowtie$}
	%
\end {theorem}

Radical Region Restriction examines each edge to be laid down individually as it is encountered
as an edge to be added to the graph.  The unified queuing parallel algorithm is
employed. Each edge is laid down in segments with each new edge segment
causing an update of the edge being laid down and a new job being created and enqueued. Those jobs
that exceeded the minimal edge length for the given edge are abandoned as they would exceed the
minimal number of crossings for the final graph being described.  The initial search algorithm and 
region restriction both use a queue.  With the implementation of Radical Region Restriction a stack 
is utilized to lay down an entire edge before moving on to the next one.  This allows for 
graphs that exceed an edge length across regions to be abandoned prior to possible generation 
of partial edge segments for other edges.

Radical Region Restriction has been used to generate minimal K$_{n}$ graphs for 
$5\le n \le10$ to date.  It is a viable tool for larger $n$ although as $n$ increases by
only a small amount it is found that long runtimes will be necessary to achieve
results.  Table~\ref{tab:radCompare} illustrates comparative runtimes of Region Restriction
and Radical Region Restriction for minimal K$_{8}$
through minimal K$_{10}$ on sixteen processors.  The jump in timing for minimal K$_{9}$ to that
of minimal K$_{10}$ is due to the number of initial feeder graphs needed.  To generate minimal
K$_{9}$ only three minimal K$_{8}$ initial feeder graphs were necessary with forty regions each.
Generation of minimal K$_{10}$ required fourteen hundred and fifty three minimal K$_{9}$ feeder 
graphs, each with sixty-five regions.  

 	\begin{table}[ht]
	\begin{center}
	\begin{tabular}{|c|r|r|r|}\hline
	{\bf Vertices} & {\bf $\nu(K_{n})$}	& {\bf Region} & \multicolumn{1}{c|}{{\bf    Radical Region}} \\
	{\bf (n)}	&		& \bf    Restriction	& {\bf Restriction} \\ \hline
		8	 & 18		& 2 hr 36 min		& 5 min \\ \hline
		9  & 36    &  $>> 1$ week  & 8 min \\ \hline
		10 & 60    &  unknown      & $\approx 1$ week \\ \hline
	\end{tabular}
	\end{center}
	\caption{Radical {\it versus} Region Restriction Timing}
	\label{tab:radCompare}
	\end{table}	
	
Refer to Section~\ref{sec:ifkn} for discussion
on initial feeder graph selection.  Chapter~\ref{chap5} discusses some possible directions for
reducing the number of regions required.  



% end section Radical

\section{Star Analysis}\label{sec:dtpl}

The parallel implementation discussed in Section~\ref{sec:pio} with the search space reductions applied to it in
Section~\ref{sec:ssr} lays down one edge segment, repackages the graph definition as a job, and
enqueues it again with the edge to be added being modified to reflect the new edge segment.  
This is done iteratively until there are no more edges to be added to the graph.  All search tree paths are
followed, with graph descriptions being built for each path as encountered.  Not every graph is a minimal
graph, but it must be built up to the point where either its number of crossings exceeds the 
current minimum number of crossings
or it is complete.  For those graphs that do exceed the current minimum number of crossings, 
the energy spent creating them is lost when they are discarded for possessing too many crossings.  
 
Radical Region Restriction and its examination of region crossings for each complete
edge, along with the fact that order of edge placement does not matter, leads to a new technique for edge
placement, Star Analysis. This technique steps away from
the iterative parallel edge segment placement and examines all the shortest complete edges that need 
to be placed.  This is accomplished through the construction of a Distance Tree and its 
associated Path List, defined in Section,~\ref{sec:dt}.
Star Analysis finds all the minimal length star graphs centered at vertex $n$ that will be
laid down onto minimal K$_{n-1}$.

Star Analysis allows for evaluation of the minimum number of crossings for K$_{n}$ from each 
region of new vertex placement in
minimal K$_{n-1}$ prior to graph construction.  For every $n$, there is not always a minimal graph
achieved with new vertex placement in every region.  Creation of Path Lists prior to any graph construction
allows for selectively choosing which graphs to construct.  Selection for minimal K$_{n}$ will focus on only
those graphs with minimal crossings across all possible graphs examined.  This technique, in addition
to allowing for exploration of the graphs with minimal crossings, also gives access to those that 
are locally minimal (graphs that have the minimal number of crossings given the region 
placement of the new vertex $n$ into minimal K$_{n-1}$ but are not globally minimal).  These graphs
are discarded as exceeding the minimal while being constructed according to the method
discussed in Section~\ref{sec:ssr}.

With star analysis, parallel jobs representing partial edge segment placement no longer exist.  
A single Distance Tree and associated Path List description are
created sequentially.  Parallelism reduces time by having multiple Distance
Tree/Path List combinations created, for each different region placement of new vertex $n$, 
simultaneously across multiple processors.  The job queuing, message passing overhead of the
previous techniques from Section~\ref{sec:ssr} are no longer of issue.

Following the introduction of Distance Trees and Path Lists in Section~\ref{sec:dt}, the selection 
of graphs for which to construct descriptions and their
construction is presented in Section~\ref{sec:gd}.

\subsection{Distance Trees and Path Lists}\label{sec:dt}

 Given a minimal K$_{n-1}$ with $r$ regions, the search for minimal K$_{n}$ proceeds
 with the placement of the new native vertex $n$ into each region of K$_{n-1}$.  As 
 stated previously, not all region placements will generate minimal K$_{n}$ for all $n$.  
 A Distance Tree is used to find the shortest region paths to each native vertex of K$_{n-1}$
 from the new native vertex $n$.  A region path is the path an edge follows through regions of
 a graph.  
 
 A Distance Tree is a full (each level is complete) tree.  It is built in a breadth-first fashion
 as follows:  (1) The tree starts with a root node.  (2) Each child node of the 
 root is then added, creating the first level of the tree.  (3) The children of the 
 first level nodes are added, creating the second level, {\it etc}, until all levels have been
 created.
 
 The root of a Distance Tree is the
 region in which the new native vertex $n$ being added to the graph K$_{n-1}$ is located.  
 Each node of the tree represents a region being crossed in the path from vertex 
 $n$ to one of the $n-1$ other native vertices of
 K$_{n}$.  Each branch of the tree represents a different complete path from the region containing 
 vertex $n$ to a region on whose boundary lies vertex $n-i$, $1 \le i \le n-1$.  The leaf, 
 terminating point, of each branch is the last region crossed to reach native vertex $n-i$.
 
 In employing breadth-first search to build the Distance Tree 
 examination is not performed on graph G but on graph H whose vertices represent the regions of G.
 Adjacent vertices of H share an edge in G.
 The source region is the region in which vertex $n$ is placed to generate K$_{n}$.  Figure~\ref{fig:reggraph}
 illustrates a minimal K$_{6}$ with its region graph.  
 
\begin{figure}[!ht]
       \begin{center}
       \includegraphics[width=5.5in]{ch3/K6RegChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{K$_{6}$ and its Region Graph Used for Breadth-First Search}
       \label{fig:reggraph}
 \end{figure}
  
 Breadth-first search is one of the simplest algorithms for searching a graph.  Given a graph H = (V,E)
 and a source vertex $u$, breadth-first search systematically computes the distance (smallest number
 of edges) from $u$ to each reachable vertex.  For any vertex $v$ reachable from $u$, the shortest
 path(s) are located.  More information related to breadth-first search and shortest-path algorithms
 is available in~\cite{clrs02}.  
 
 Because each vertex of H, and hence, each node of the Distance Tree, represents a region of G, the
 region restriction stated in Lemma~\ref{lm:noback} in Section~\ref{sec:rr} can be restated 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}

Lemma~\ref{lm:noback} restated in terms of Distance Tree Region Restriction becomes as follows:
 
 \begin{theorem}\label{th:DTrr}
	In generating a Distance Tree for minimal K$_{n}$ from minimal K$_{n-1}$ as described, 
	the use of the Distance Tree Region Restriction
	does not eliminate any possible minimal graphs from being generated.
	\end{theorem}
	
Once one complete level of the Distance Tree is constructed, all regions
on that level are restricted from appearing in any branch of the tree at any later level.  
 
  \begin{figure}[!ht]
       \begin{center}
 
         \includegraphics[width=5.5in]{ch3/BegDistTreeChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Beginning Distance Tree for One Minimal K$_{6}$}
       \label{fig:begDT}
 \end{figure}
 
 The following series of figures will illustrate the process of building the Distance Tree given
 minimal K$_{6}$ with native vertex 7 placement in region R9.  Figure~\ref{fig:reggraph} shows the
 minimal K$_{6}$ with the vertices and regions labeled for this discussion.
 In viewing Figure~\ref{fig:reggraph} notice that two native vertices, 3 and 6, can be 
 directly connected to vertex 7 
 without any crossings.  These directly connected vertices are not included in the Distance Tree
 but are addressed in the Path List construction at the end of this section.  Crossings will 
 be generated in connecting vertex 7 to the remaining four vertices 1, 2, 4 
 and 5.  Region R9 has three edges on its boundary, each possible as a crossing from vertex 7.
 Thus, three branches emanate from the root representing region R9.  Figure~\ref{fig:begDT} illustrates
 the root and the three initial branches.  In addition to the region traveled to, the tree
 must remember the edge crossed in getting there so the path can be recreated.  This edge
 information is reflected in Figure~\ref{fig:begDT} also.  Notice that there are two direct 
 connections possible through the level 1 regions R12 and R11 {\it via} the crossing edges (3,9) and 
 (6,9) to vertices 2 and 5, respectively.  Regions R11 and R12 are terminal leaves in the tree for
 their paths from Region R9 to vertices 2 and 5.  Level 1 of the Distance Tree is complete.  
 
 With each level of the tree encountered, there is at least one
 crossing that will be reflected in the K$_{7}$ graph being considered.  With vertices 2 and 5 on
 the boundaries of regions at Level 1, there will be two new crossings to add to the already existing
 three crossings of minimal K$_{6}$ in the hunt for minimal K$_{7}$. 
 More levels, implying more crossings, are necessary to connect to vertices 1 and 4.
 
 
 Figure~\ref{fig:level2DT} shows the addition of Level 2 to the Distance Tree construction
 being illustrated.  Level 2 indicates that two crossings are necessary to get to any  
 vertex on the boundary of a region at this level.  Both vertex 1
 and vertex 4 lie on the boundaries of regions that appear at level 2.  Thus, for each of 
 these vertices, 2 crossings will be 
 necessary in connecting them to vertex 7.  Adding these 4 crossings to the existing 5
 tells us that a minimal K$_{7}$ with nine crossings can be constructed from the
 minimal K$_{6}$ shown in Figure~\ref{fig:reggraph} with vertex 7 placed in Region R9.  
   
  \begin{figure}[!ht]
       \begin{center}
       \includegraphics[width=5.5in]{ch3/FinalDistTreeChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Distance Tree for One Minimal K$_{6}$}
       \label{fig:level2DT}
 \end{figure}
 
 Figure~\ref{fig:level2DT} also illustrates that for this example, vertices 1 and 4 each 
 have two paths possible from the root Region R9.  Considering all possible path combinations,
 there are four minimal K$_{7}$ graphs, each with nine crossings,
 described in this one Distance Tree.
 
 Because edges of the Distance Tree correspond to crossings in the K$_{n}$ construction, it would be
 possible to terminate the Distance Tree construction if that crossing count should exceed an
 upper bound, such as Guy's Conjecture~\ref{th:Kn}.  Or, the Distance Trees can be created and
 all local crossing numbers will be determined.  
 
 Returning to the issue of the Distance Tree Region Restriction introduced with 
 Definition~\ref{def:DTrr} and Theorem~\ref{th:DTrr}, refer to Figure~\ref{fig:regnbr}, and note that in 
 the search for the shortest path from vertex 7 to all other native vertices 
 $n-i$, $1 \le i \le n-1$, region exploration takes place in an expanding
 fashion starting with the initial region (labeled ``start'' in this illustration) and working outward to 
 neighboring regions until connections to all vertices $n-i$ are made.  From the starting region, 
 progress moves out to regions immediately adjacent from level to level.  Level 2 regions are
 the neighbors of regions R11, R12, and R13 that have not yet been visited, namely regions 
 R2, R3, R4, R8,and R10.  Higher level regions can be determined similarly.  As noted previously, once a 
 region appears in a level, it cannot appear again in any other level.
  
  \begin{figure}[!ht]
       \begin{center}
        \includegraphics[width=4.0in]{ch3/regExpansionChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Outward Expanding Region Neighborhoods}
       \label{fig:regnbr}
 \end{figure}
 
 	The paths from vertex $n$ to vertices $n-i$ represented in a given Distance Tree hold
	all the shortest path information for at least one K$_{n}$ that is minimal, though
	possibly only locally minimal.  These paths are saved in Path List descriptions as described
	below for future analysis and minimal K$_{n}$ graph description 
	construction.  
	
	For each initial minimal K$_{n-1}$ graph description and source region, 
	the paths from the Distance Tree with the minimum number of crossings are saved as a unit in 
	a Path List description.  The Path Lists are available for future graph description 
	construction or other analysis.
	
	A Path List is a list of all the possible paths found in the Distance Tree.  Recall that
	vertices on the boundary of the region in which vertex $n$ was placed are 
	not considered in the
	Distance Tree.  Instead they are included in the Path List.
	
	The
	Distance Tree in Figure~\ref{fig:level2DT} can been seen to reflect directly to the Path List
	in Figure~\ref{fig:plist}.  Reading the first line notice that the path starts in region R9 and 
	crosses edge (6,3) to enter region R13.  From region 13 edge (6,10) is crossed to region R8 from which
	a direct connection is made to vertex 1.  As seen in the Path List, there are two shortest paths
	to vertices 1 and 4.  Also note the two direct connection paths with no crossings for
	vertices 3 and 6. 
	 
  \begin{figure}[!ht]
       \begin{center}
       \includegraphics[width=4.0in]{ch3/PathListChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Path List for Minimal K$_{7}$}
       \label{fig:plist}
 \end{figure}  

	A Path List description contains all the information necessary to describe a minimal, although possibly only locally
	minimal, K$_{n}$.  If the goal is to generate global minimal K$_{n}$, across all K$_{n}$, those Path
	List descriptions with the minimum number of crossings are used to generate graph descriptions for all the
	graphs possible to construct from all possible combinations of the paths in the Path List.
	
	
	This section has explained the construction of the Distance Tree for K$_{n}$ given an
	initially minimal	K$_{n-1}$.  All shortest paths from vertex $n$ to each vertex $n-i$, 
	$1 \le i \le n-1$, are described in the Path List for the given minimal K$_{n-1}$ and
	region of vertex $n$ placement.
	For any initial graph and region placement for a new vertex, the Path List description makes
	all locally minimal  shortest paths available for analysis.  The ability is now available to examine the
	regions supporting the same local minimum across, or within, graphs, path length statistics,
	{\it etc}.. 

\subsection{Graph Descriptions from Path Lists}\label{sec:gd}

	Once all the Path List descriptions are created for a given input set, the selection of the 
	set of graphs for which to build descriptions presents itself. For example, the input set might
	be all minimal K$_{7}$ with vertex placement in each possible region (there are 25 regions).
	Generating Path List files for this input set would supply all shortest path K$_{8}$ possible
	with the number of crossings seen if the graphs were to be constructed.  Given the goal of 
	constructing all minimal K$_{8}$, only those Path List files with the minimum number of 
	crossings would be examined.  In addition to the ability to look at just global
	minimal graphs, this technique allows for the building of graph descriptions of all shortest
	path K$_{8}$ graphs.
	
	To illustrate the construction of graph descriptions, refer to Figure~\ref{fig:plist}. Four minimal
	K$_{7}$ graphs can be constructed from this path list.  The process of constructing one of the four
	is presented.
	
	Figure ~\ref{fig:K6toK7} shows a minimal K$_{7}$ as constructed from the initial K$_{6}$ 
	of Figure~\ref{fig:reggraph} with vertex $7$ placed in region 9.  The Path List of Figure~\ref{fig:reggraph}
	contains one path to each of vertices 2, 3, 5, and 6.  
	The first paths to vertex 1 and vertex 4 from the path list are used with
	the only paths to vertices 2, 3, 5, and 6 to describe the first star graph that we place on K$_{6}$.  
	Each $n-(n-i)$ path is laid down edge by edge, segment by segment onto minimal K$_{6}$ 
	to arrive at this minimal K$_{7}$.  
	 
  \begin{figure}[!t]
       \begin{center}
         \includegraphics[width=4.0in]{ch3/K7FromK6Chap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Minimal K$_{7}$ from Minimal K$_{6}$}
       \label{fig:K6toK7}
 \end{figure} 
  
	At this time, it cannot be stated that a mathematical calculation of the number of ways 
	the different $n-1$ paths may be combined definitively indicates the exact number of 
	graphs defined by a Path List.  It is possible that some combinations may lead to 
	graphs that do not meet the definition of a good graph.  An example of what 
	may theoretically occur is as follows.
	
	Figure~\ref{fig:badEdges} shows a portion of a hypothetical graph with possible Path Lists
	from vertex $n$ to vertices 4 and 5. All combinations of paths are shown on the figure.
	All combinations of paths $n$-$4$ and $n$-$5$ cannot
	be used together.  The two paths highlighted by stars (*) may not be placed together on the
	graph.  If they were, they would cross, and the graph would fail to be good.  
	Figure~\ref{fig:goodPlacement} illustrates examples of paths P1 and P4 used in valid 
	$n$-$4$, $n$-$5$ path combinations.
		 
  \begin{figure}[!ht]
       \begin{center}
         \includegraphics[width=4.5in]{ch3/BadEdgesChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{A Hypothetical Path List Conflict}
       \label{fig:badEdges}
 \end{figure}  
  
		 
  \begin{figure}[!ht]
       \begin{center}
       \includegraphics[width=4.5in]{ch3/goodChap3.pdf}
         % [width=#in]
         % [height=#in]
       \end{center}
       \caption{Two Different Non-conflicting Placement of Paths}
       \label{fig:goodPlacement}
 \end{figure}  
 
 Refer to~\cite{Hump2006:tba} for further details on the implementation of 
 Path Lists and Graph Description construction.  With the development of Star Analysis 
 complete, the discussion turns in Chapter~\ref{chap4} to the process of
 iteratively growing minimal K$_{n}$ from minimal K$_{n-1}$.  
         
	    



