\defn\id{density}%
Let $G$ be a~graph and $\cal C$ be a class of graphs. We define the \df{edge density}
$\varrho(G)$ of~$G$ as the average number of edges per vertex, i.e., $m(G)/n(G)$. The
-edge density $\varrho(\cal C)$ of the class is then defined as the infimum of $\varrho(G)$ over all $G\in\cal C$.
+edge density $\varrho(\cal C)$ of the class is then defined as the supremum of $\varrho(G)$ over all $G\in\cal C$.
\thmn{Mader \cite{mader:dens}}\id{maderthm}%
For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph
Let us return to the analysis of our algorithm.
-\thmn{MST on minor-closed classes, Mare\v{s} \cite{mm:mst}}\id{mstmcc}%
+\thmn{MST on minor-closed classes, Tarjan \cite{tarjan:dsna}}\id{mstmcc}%
For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's
algorithm (\ref{contbor}) finds the MST of any graph of this class in time
$\O(n)$. (The constant hidden in the~$\O$ depends on the class.)
\figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}}
\rem
-The observation in~Theorem~\ref{mstmcc} was also independently made by Gustedt \cite{gustedt:parallel},
-who studied a~parallel version of the Contractive Bor\o{u}vka's algorithm applied
+The observation in~Theorem~\ref{mstmcc} was also used by Gustedt \cite{gustedt:parallel},
+to construct parallel version of the Contractive Bor\o{u}vka's algorithm applied
to minor-closed classes.
\rem
\algin A~graph~$G$ with an edge comparison oracle.
\:$T\=\emptyset$. \cmt{edges of the MST}
\:$\ell(e)\=e$ for all edges~$e$. \cmt{edge labels as usually}
-\:$m_0\=m$.
+\:$m_0\=m$. \cmt{in the following, $n$ and $m$ will change with the graph}
\:While $n>1$: \cmt{We will call iterations of this loop \df{phases}.}
\::$F\=\emptyset$. \cmt{forest built in the current phase}
\::$t\=2^{\lceil 2m_0/n \rceil}$. \cmt{the limit on heap size}
The Iterated Jarn\'\i{}k's algorithm runs in time $\O(m\log^* n)$.
\proof
-$\beta(m,n) \le \beta(1,n) \le \log^* n$.
+$\beta(m,n) \le \beta(n,n) \le \log^* n$.
\qed
\cor\id{ijdens}%