Compressing Cell MSTs into Trajectory Skeletons

Why Compress a Cell-Level Tree?

A cell minimum spanning tree can contain many vertices whose only role is to connect one cell to the next along an otherwise unbranched route. Drawing every such vertex makes a trajectory difficult to read, even when the scientific question concerns only the broad routes and branch structure. A trajectory skeleton summarizes these routes as segments and retains the locations where routes begin, end, or meet.

The key requirement is to simplify the representation without changing the tree’s topology. In this tutorial, topology means the connectivity and branching relationships of the graph, not its precise shape in an embedding. Compression should therefore remove only vertices that lie inside unbranched paths. A leaf or a branchpoint is structurally meaningful and must remain.

This definition applies to the graph after the MST has been constructed. It does not decide which edge weights or cell geometry should have been used to build that tree. The earlier material on constructing minimum spanning trees and choosing edge weights concerns those upstream choices. Here, the fixed input is a tree, and the task is to represent its structure more compactly.

A segment can retain more than its two endpoint labels. For an original path \(v_0,v_1,\ldots,v_m\), it can store the ordered list of cells along the path, the number of edges, and an aggregate of the edge weights. If the weights \(w_i\) represent additive distances or costs, a natural segment weight is \(W=\sum_{i=1}^{m}w_i\). The internal vertices are omitted from the drawing of the skeleton, not erased from the data or reassigned to a different route.

What Compression Preserves

In a finite tree with at least two vertices, leaves and vertices of degree at least 3 are precisely the vertices retained by the rule. Every other vertex has degree 2 and lies along a unique unbranched route. Because the input is connected and acyclic, there is exactly one path between any two vertices. Thus each maximal degree-2 chain has a well-defined pair of retained endpoints and becomes one segment between them.

Compression preserves which retained vertices are connected by each route. In particular, it preserves the number of leaves, the degree of every retained branchpoint, and the incidence pattern among endpoints and branchpoints. It does not preserve the number or identities of internal cells unless those are stored as segment metadata. Nor does it automatically preserve a geometric curve between cells: a segment weight gives an aggregate, not the detailed positions or shape of the path.

To justify the result, consider replacing one degree-2 vertex \(u\), adjacent to \(a\) and \(b\), by an edge between \(a\) and \(b\). Any route that formerly passed through \(u\) can now use the replacement edge, so connectivity among the remaining vertices is unchanged. A cycle in the new graph would correspond to a cycle in the original graph by expanding the replacement edge back to the path \(a-u-b\); this is impossible because the original graph is acyclic. Repeating this operation along each maximal chain gives the skeleton. No leaf or branchpoint is removed, so their incidences remain represented.

For a tree with at least two vertices, let \(L\) be its number of leaves and \(B\) its number of branchpoints. The skeleton has \(L+B\) vertices and therefore \(L+B-1\) edges, because every finite tree with \(q\) vertices has \(q-1\) edges. This is a useful bookkeeping check. A one-vertex tree is a special case: it has one retained vertex and no segments.

Constructing and Checking the Skeleton

A practical procedure is to compute degrees from the fixed MST, mark all vertices of degree other than 2, then trace each edge out of a marked vertex through degree-2 vertices until another marked vertex is reached. Mark each original edge as visited so it belongs to exactly one segment. For every segment, retain its endpoints, ordered path, edge count, and chosen weight summary. These records make it possible to inspect or reconstruct the original path.

A branchpoint in a tree may have degree 4 or higher; it should remain one vertex with that degree. Replacing it with a sequence of degree-3 vertices would invent a branching order not present in the input. Likewise, do not collapse two branchpoints into one merely because they are close in the embedding: their connection may contain a short segment, but the distinct branch incidences are part of the topology.

Weight Summaries and Meaning

Topology does not depend on the numerical values of the edge weights once the MST has been fixed. The degree rule identifies the same vertices whether the weights are Euclidean distances, another nonnegative dissimilarity, or omitted from the drawing. Weight summaries matter for the metric information attached to segments, however. If edge weights measure additive path distance, summing them gives the path length. If weights are similarities, probabilities, or another non-additive quantity, their sum may have no meaningful interpretation; retain the edge-level values or define a justified alternative summary instead.

Diagnostics, Alternatives, and Limitations

Several checks can reveal a faulty compression. If the skeleton has fewer or more leaves than the input, an endpoint may have been removed or misclassified. If a branchpoint’s degree changes, a segment may have been traced incorrectly or multiple junctions may have been merged. If any input edge is missing or counted in two segments, path tracing is incomplete. For a nontrivial tree, the number of segments should equal the number of retained vertices minus one, and each segment should expand to a unique path in the original tree.

Compression also cannot repair a questionable MST. A spurious branch remains a branchpoint if its degree is at least 3; deciding whether to remove such a branch is a separate modeling choice. Similarly, a disconnected input is not made into a single trajectory by drawing its components close together. The tree assumption must be checked before interpreting the skeleton.

The full MST is preferable when cell identities, local edge lengths, or short-scale irregularities are central to the question. A skeleton is preferable for a compact account of branch incidence and long routes, provided its segments retain sufficient metadata. A principal curve instead represents a smooth geometric path and is not simply a compressed graph; it may be unsuitable for representing genuine branching. These representations answer related but distinct questions, and none of them by itself establishes a biological lineage or causal direction.

A common mistake is to say, “Degree-2 cells contain no information, so delete them.” Degree 2 means only that a vertex does not change the tree’s branching pattern. The cells can still carry expression states, annotations, or local geometry relevant to interpretation. The correction is to suppress them only in the skeleton display or data structure while keeping a mapping from every segment to its original cells and edges whenever those details may matter.