Hubbry Logo
Strahler numberStrahler numberMain
Open search
Strahler number
Community hub
Strahler number
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Strahler number
Strahler number
Strahler number
View on Wikipedia
from Wikipedia
Diagram showing the Strahler stream order

In mathematics, the Strahler number or Horton–Strahler number of a mathematical tree is a numerical measure of its branching complexity.

These numbers were first developed in hydrology, as a way of measuring the complexity of rivers and streams, by Robert E. Horton (1945) and Arthur Newell Strahler (1952, 1957). In this application, they are referred to as the Strahler stream order and are used to define stream size based on a hierarchy of tributaries. The same numbers also arise in the analysis of L-systems and of hierarchical biological structures such as (biological) trees and animal respiratory and circulatory systems, in register allocation for compilation of high-level programming languages and in the analysis of social networks.

Definition

[edit]

All trees in this context are directed graphs, oriented from the root towards the leaves; in other words, they are arborescences. The degree of a node in a tree is just its number of children. One may assign a Strahler number to all nodes of a tree, in bottom-up order, as follows:

  • If the node is a leaf (has no children), its Strahler number is one.
  • If the node has one child with Strahler number i, and all other children have Strahler numbers less than i, then the Strahler number of the node is i again.
  • If the node has two or more children with Strahler number i, and no children with greater number, then the Strahler number of the node is i + 1.

The Strahler number of a tree is the number of its root node.

Algorithmically, these numbers may be assigned by performing a depth-first search and assigning each node's number in postorder. The same numbers may also be generated via a pruning process in which the tree is simplified in a sequence of stages, where in each stage one removes all leaf nodes and all of the paths of degree-one nodes leading to leaves: the Strahler number of a node is the stage at which it would be removed by this process, and the Strahler number of a tree is the number of stages required to remove all of its nodes. Another equivalent definition of the Strahler number of a tree is that it is the height of the largest complete binary tree that can be homeomorphically embedded into the given tree; the Strahler number of a node in a tree is similarly the height of the largest complete binary tree that can be embedded below that node.

Any node with Strahler number i must have at least two descendants with Strahler number i − 1, at least four descendants with Strahler number i − 2, etc., and at least 2i − 1 leaf descendants. Therefore, in a tree with n nodes, the largest possible Strahler number is log2 n + 1.[1] However, unless the tree forms a complete binary tree its Strahler number will be less than this bound. In an n-node binary tree, chosen uniformly at random among all possible binary trees, the expected index of the root is with high probability very close to log4 n.[2]

Applications

[edit]

River networks

[edit]

In the application of the Strahler stream order to hydrology, each segment of a stream or river within a river network is treated as a node in a tree, with the next segment downstream as its parent. When two first-order streams come together, they form a second-order stream. When two second-order streams come together, they form a third-order stream. Streams of lower order joining a higher order stream do not change the order of the higher stream. Thus, if a first-order stream joins a second-order stream, it remains a second-order stream. It is not until a second-order stream combines with another second-order stream that it becomes a third-order stream. As with mathematical trees, a segment with index i must be fed by at least 2i − 1 different tributaries of index 1. Shreve noted that Horton's and Strahler's Laws should be expected from any topologically random distribution. A later review of the relationships confirmed this argument, establishing that, from the properties the laws describe, no conclusion can be drawn to explain the structure or origin of the stream network.[3][4]

To qualify as a stream a hydrological feature must be either recurring or perennial. Recurring (or "intermittent") streams have water in the channel for at least part of the year. The index of a stream or river may range from 1 (a stream with no tributaries) to 12 (globally the most powerful river, the Amazon, at its mouth). The Ohio River is of order eight and the Mississippi River is of order 10. Estimates are that 80% of the streams on the planet are first to third order headwater streams.[5]

If the bifurcation ratio of a river network is high, then there is a higher chance of flooding. There would also be a lower time of concentration.[6] The bifurcation ratio can also show which parts of a drainage basin are more likely to flood, comparatively, by looking at the separate ratios. Most British rivers have a bifurcation ratio of between 3 and 5.[7]

Comparison of incorrect and correct conversion of water bodies to a tree network

Gleyzer et al. (2004) describe how to compute Strahler stream order values in a GIS application. This algorithm is implemented by RivEX, an ESRI ArcGIS Pro 3.4.x tool. The input to their algorithm is a network of the centre lines of the bodies of water, represented as arcs (or edges) joined at nodes. Lake boundaries and river banks should not be used as arcs, as these will generally form a non-tree network with an incorrect topology.

Alternative stream ordering systems have been developed by Shreve[8][9] and Hodgkinson et al.[3] A statistical comparison of Strahler and Shreve systems, together with an analysis of stream/link lengths, is given by Smart.[10]

Other hierarchical systems

[edit]

The Strahler numbering may be applied in the statistical analysis of any hierarchical system, not just to rivers.

  • Arenas et al. (2004) describe an application of the Horton–Strahler index in the analysis of social networks.
  • Ehrenfeucht, Rozenberg & Vermeir (1981) applied a variant of Strahler numbering (starting with zero at the leaves instead of one), which they called tree-rank, to the analysis of L-systems.
  • Strahler numbering has also been applied to biological hierarchies such as the branching structures of trees[11] and of animal respiratory and circulatory systems.[12]

Register allocation

[edit]

When translating a high-level programming language to assembly language the minimum number of registers required to evaluate an expression tree is exactly its Strahler number. In this context, the Strahler number may also be called the register number.[13]

For expression trees that require more registers than are available, the Sethi–Ullman algorithm may be used to translate an expression tree into a sequence of machine instructions that uses the registers as efficiently as possible, minimizing the number of times intermediate values are spilled from registers to main memory and the total number of instructions in the resulting compiled code.

[edit]

Bifurcation ratio

[edit]

Associated with the Strahler numbers of a tree are bifurcation ratios, numbers describing how close to balanced a tree is. For each order i in a hierarchy, the ith bifurcation ratio is

where ni denotes the number of nodes with order i.

The bifurcation ratio of an overall hierarchy may be taken by averaging the bifurcation ratios at different orders. In a complete binary tree, the bifurcation ratio will be 2, while other trees will have larger bifurcation ratios. It is a dimensionless number.

Pathwidth

[edit]

The pathwidth of an arbitrary undirected graph G may be defined as the smallest number w such that there exists an interval graph H containing G as a subgraph, with the largest clique in H having w + 1 vertices. For trees (viewed as undirected graphs by forgetting their orientation and root) the pathwidth differs from the Strahler number, but is closely related to it: in a tree with pathwidth w and Strahler number s, these two numbers are related by the inequalities[14]

w ≤ s ≤ 2w + 2.

The ability to handle graphs with cycles and not just trees gives pathwidth extra versatility compared to the Strahler number. However, unlike the Strahler number, the pathwidth is defined only for the whole graph, and not separately for each node in the graph.

See also

[edit]

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Strahler number

View on Grokipedia
from Grokipedia
The Strahler number, also known as the Horton–Strahler number, is a hierarchical ordering system used primarily in and to quantify the branching complexity of river networks by assigning orders to streams based on their structure. Developed initially by Robert E. Horton in 1945 as part of a hydrophysical approach to analyzing morphology, it was refined by Arthur N. Strahler in 1957 to provide a more standardized method for classifying stream segments from headwaters to main channels. In this system, the smallest, unbranched headwater streams—those without —are designated as order 1; when two streams of equal order join, the resulting downstream segment receives the next higher order (e.g., two order-1 streams form an order-2 stream); however, if streams of unequal orders , the downstream order matches the higher of the two incoming orders without incrementing. This ordering scheme facilitates the analysis of properties, such as length distributions, basin shape, and relief ratios, enabling quantitative comparisons across watersheds for studies, flood prediction, and . Beyond , the Strahler number has been generalized in and as a measure of graph complexity, where it evaluates the depth of binary branching in rooted trees, with applications in algorithm analysis, phylogenetic modeling, and . The highest order in a network often correlates with basin size and complexity, typically ranging from 3 to 10 in natural systems.

Definition and Fundamentals

Formal Definition

The Strahler number, also known as the Horton–Strahler number, is a measure of branching defined on rooted trees, which are directed acyclic graphs consisting of a single root node with edges directed away from the root and no directed cycles. The Strahler number is assigned recursively to each node in the tree. All leaf nodes (those with no children) are assigned the Strahler number 1. For a non-leaf node, let ii be the maximum Strahler number among its children. The node is then assigned the Strahler number ii if exactly one child has Strahler number ii (and all others have strictly smaller values); otherwise, if two or more children have Strahler number ii, the node is assigned i+1i + 1. The Strahler number of the entire , denoted S(T)S(T) for a rooted TT, is the value assigned to the node. This measure is equivalent to the Horton–Strahler used in to quantify the hierarchical structure of river networks.

Illustrative Examples

To illustrate the Strahler number, consider simple tree structures where the assignment proceeds bottom-up, starting with leaves labeled as order 1 and propagating orders to internal nodes based on the maximum order among children, incrementing only when multiple children share that maximum. A linear tree, or , consisting of a single sequence of n nodes from to with no branching, has a Strahler number of 1 at every node, as there are never multiple children to trigger an increment. For example, in a of three nodes—root connected to an internal node connected to a —the receives order 1, the internal node inherits 1 from its single child, and the inherits 1 similarly. In contrast, a complete of h, where every level is fully filled and all leaves are at depth h, has a Strahler number of h at the , with orders increasing uniformly by 1 at each level due to symmetric branching. This reflects the balanced case where the Strahler number equals the tree's . For an unbalanced tree, consider a with three direct subtrees: one is a single (order 1), and the other two are each complete binary trees of 1 (roots with two leaves each, yielding order 2 for those subroots). The bottom-up assignment begins with all leaves labeled 1; the two subroots then each receive order 2, as they have two children of order 1; finally, the main has children of orders 1, 2, and 2, so its order is the maximum (2) incremented by 1 to 3, since two children share that maximum. This labeling highlights how asymmetry in branching affects the overall order without proportional depth increase.

Historical Development

Origins in Hydrology

The concept of stream ordering, which laid the groundwork for the , was first introduced by Robert E. Horton in his paper on the erosional development of and . Horton proposed a system for within a , defining based on the branching structure and introducing the bifurcation ratio as a quantitative measure of how stream numbers decrease with increasing order. This approach aimed to provide a for analyzing basin morphology, emphasizing the role of networks in erosion processes and overall landscape evolution. Arthur N. Strahler built upon Horton's ideas, formalizing the system in his 1957 quantitative analysis of watershed . There, he established a rule where the order of a segment increases only when two streams of the same order join, creating a higher-order channel otherwise. These refinements shifted the focus from qualitative descriptions to a more objective, numerical scheme for classifying hierarchies, enabling precise evaluations of basin geometry, erosional dynamics, and potential. The motivation stemmed from the need to quantify characteristics to predict hydrological behaviors, such as water flow patterns and , which were critical for studies. By the 1960s, Strahler's stream ordering system had gained widespread adoption in hydrological research and mapping efforts. This integration facilitated standardized topographic mapping and supported the development of predictive tools for erosion and flooding risks in diverse watersheds.

Adoption and Extensions

Following its initial formulation in hydrology, the Strahler number underwent mathematical formalization in graph theory and combinatorics during the 1970s and 1980s, where it was recognized as a measure of branching complexity applicable to abstract tree structures. In 1979, Philippe Flajolet, Jean-Luc Raoult, and Jean Vuillemin analyzed the distribution of Strahler numbers in binary trees, connecting the concept to stack depth and register requirements in computational processes. This work highlighted its utility in evaluating tree shapes for algorithmic efficiency. Concurrently, in 1981, N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou established a link between the Strahler number and pathwidth in undirected trees, equating the former to the search number needed to clear a graph of contaminants, thus integrating it into broader graph searching paradigms. In , the Strahler number was independently rediscovered as the "register function" for optimizing in , particularly for evaluating arithmetic expressions represented as trees. This connection traces back to Ershov's 1958 work on the minimal number of registers required, later formalized in the Sethi–Ullman (1970), which computes labeling equivalent to Strahler numbers to minimize spills during code generation. By the 1980s, these insights influenced compiler design, with the Strahler-based labeling ensuring optimal register usage for binary operator trees. From the 1990s onward, extensions proliferated into formal language theory and modeling applications. In 1979, Andrzej Ehrenfeucht, Grzegorz Rozenberg, and Dirk Vermeir introduced tree-rank—a variant of the Strahler number—for analyzing derivation trees in ET0L systems, a class of parallel rewriting systems akin to L-systems used for simulating plant morphogenesis and branching patterns. This facilitated quantitative assessment of structural complexity in developmental models. Similarly, the Strahler number found application in , where it quantifies hierarchical branching in affiliation networks and communication trees, as explored in recent combinatorial studies. Key milestones in practical adoption include its integration into geographic information systems (GIS) during the 2000s. , developed by , incorporated Strahler ordering in its Spatial Analyst toolbox for automated stream network delineation from digital elevation models, enabling efficient classification of drainage hierarchies in geospatial datasets. Theoretically, Luc Devroye and Pawel Kruszewski's 1995 analysis of Strahler numbers in random binary trees provided asymptotic results on expected values and variances, influencing probabilistic models of tree growth. Recent extensions, particularly as of 2025, have advanced probabilistic interpretations on Galton–Watson trees. For instance, Robin Khanfir's work derives limit theorems for the Strahler number under stable offspring distributions, conditioning on tree size. Similarly, updated analyses by Khanfir and others on Galton–Watson trees with infinite variance establish central limit theorems, bridging branching processes with hydrological laws. These contributions, often disseminated via , underscore ongoing interdisciplinary growth beyond pre-2021 literature.

Computation and Properties

Algorithms for Calculation

The Strahler number of a can be computed using a recursive based on post-order traversal, such as , which processes the tree bottom-up from the leaves to the root. For a leaf node (with no children), the Strahler number is assigned as 1. For an internal node, the Strahler number is determined by examining the Strahler numbers of its children: let mm be the maximum Strahler number among the children; if exactly one child has Strahler number mm, then the node's Strahler number is mm; otherwise (if two or more children have mm), it is m+1m + 1. This approach operationalizes the branching measure by propagating orders upward, ensuring that confluences of high-order branches increase the order only when multiple equivalent maxima merge. The recursive procedure can be expressed in pseudocode as follows:

function Strahler(node): if node has no children: return 1 child_orders = [Strahler(child) for child in node.children] m = max(child_orders) count_max = number of children with order m if count_max >= 2: return m + 1 else: return m

function Strahler(node): if node has no children: return 1 child_orders = [Strahler(child) for child in node.children] m = max(child_orders) count_max = number of children with order m if count_max >= 2: return m + 1 else: return m

This function computes the Strahler number for the root node upon invocation. An alternative interpretation of the Strahler number, particularly for , views it as the number of iterative steps required to reduce the to a single node by repeatedly removing all leaves. Each iteration eliminates terminal nodes, simulating the successive merging of branches, and the total iterations equal the root's Strahler number. This provides an intuitive, non-recursive way to verify the value, though it is less efficient for direct computation compared to the recursive traversal. The recursive algorithm achieves linear , O(n)O(n), where nn is the number of nodes in the , as it visits each node and edge exactly once during the depth-first traversal. Similar efficiency holds for implementations in river network analysis software, where vector-based recursive ordering handles braided structures in O(n)O(n) time. The algorithm extends naturally to more general structures, such as directed acyclic graphs (DAGs) and arborescences, by performing a topological sort to ensure bottom-up processing of nodes and applying the same merging rule to incoming edges treated as children. In DAGs, this may involve transforming the graph into an equivalent or tracking register usage to handle shared substructures, maintaining O(n)O(n) complexity where nn counts edges.

Key Mathematical Properties

The Strahler number S(T)S(T) of a TT with nn nodes satisfies the upper bound S(T)≤⌈log⁡2n⌉S(T) \leq \lceil \log_2 n \rceil, which is achieved in complete balanced binary trees where the structure maximizes branching at each level. This bound arises because the Strahler number increases by at most 1 per level of the tree, limiting its value relative to the logarithm of the node count in optimally branched configurations. In random models, the expected Strahler number exhibits . For uniform random binary trees with nn internal nodes, the expectation satisfies E[Sn]≈log⁡4n\mathbb{E}[S_n] \approx \log_4 n, with variance bounded by a constant, implying concentration around this mean. For conditioned Galton-Watson trees, recent refines this to E[S(Tn)]=log⁡4n+D(log⁡4n)+o(1)\mathbb{E}[S(T_n)] = \log_4 n + D(\log_4 n) + o(1), where DD is a continuous 1-periodic function, again with sub-logarithmic fluctuations. Key properties include invariance under edge subdivision, meaning the Strahler number remains unchanged when refining the by inserting degree-2 vertices along edges, as the branching structure is preserved topologically. Additionally, S(T)≤h(T)S(T) \leq h(T), where h(T)h(T) is the of TT, since the number increments by at most 1 across levels. The Strahler number also equals the minimum number of registers required to evaluate the corresponding arithmetic expression minus one, linking it to in compilation. Recent theoretical advances address probabilistic branching models. In butterfly trees—constructed via recursive gluing of substructures—the Horton-Strahler number concentrates tightly near its upper bound ⌊log⁡4N⌋\lfloor \log_4 N \rfloor, with a establishing Gaussian fluctuations around the mean for simple cases, filling gaps in exact distributional analysis for such self-similar trees.

Applications

River Networks and

In river networks, the Strahler number serves as a hierarchical measure to classify based on their branching structure, where unbranched headwater are designated as (order 1). When two of the same order converge, the resulting downstream segment receives an order one higher than the incoming ; if of different orders meet, the order remains that of the higher-order . This system quantifies the complexity and scale of fluvial systems, with higher-order representing larger, more integrated channels that accumulate drainage from extensive upstream areas. Representative examples illustrate the scale of Strahler ordering in major basins; for instance, the , the world's largest by discharge, achieves a Strahler order of 12 at its mouth, reflecting its vast network spanning multiple continents. In typical river basins, approximately 80% of the total stream length consists of first- to third-order headwater streams, which dominate the network despite their small individual sizes and play a critical role in overall hydrological processes. These low-order streams often exhibit high variability in flow and , contrasting with the more stable, higher-order channels downstream. Strahler numbers find key applications in for assessing basin and predicting dynamics, as higher-order streams indicate larger contributing areas prone to amplified runoff and inundation during extreme events. For example, delineating -prone zones in urban subbasins relies on Strahler ordering to identify segments where confluence-driven increases in order correlate with elevated risk, enabling targeted without full hydraulic modeling. This integrates with Horton's laws, which describe geometric progressions in numbers, lengths, and areas across orders, allowing predictions of basin-wide propagation based on hierarchical . In natural rivers, the average bifurcation ratio—derived from Strahler orders as the ratio of numbers between consecutive orders—hovers around 4, signifying consistent branching patterns that influence hydrological response times and rates. Geographic information systems (GIS) facilitate Strahler analysis through automated tools, such as those in , which compute orders from digital elevation models and differentiate the Strahler method from alternatives like Shreve ordering, where magnitudes accumulate additively at confluences rather than hierarchically. The Strahler approach is preferred for geomorphological studies due to its emphasis on topological , aiding in basin geometry assessments aligned with Horton's principles.

Biological and Social Hierarchies

The Strahler number has been applied to model the hierarchical branching in biological structures, providing a measure of analogous to river networks but adapted to organic systems without fluid flow dynamics. In mammalian lungs, the bronchial exhibits asymmetric branching, with Strahler orders typically ranging from 1 to 11 in humans, where terminal bronchioles are order 1 and the trachea is order 11, encompassing approximately 25,000 terminal branches across these orders. Similar ordering reveals 10 Strahler orders in ovine lungs, highlighting evolutionary variations in airway among mammals. For pulmonary vascular systems, the arterial in humans spans 12 Strahler orders, while the venous covers 10 orders, down to capillary equivalents, enabling analysis of distribution efficiency. In root systems, the Strahler-based topological scaling quantifies branching from tips (order 1) upward, revealing self-similar patterns that influence nutrient uptake; for instance, studies on forest s show linear relationships between Strahler order and root diameter or length, with higher orders corresponding to thicker axial roots. In social sciences, the Strahler number quantifies hierarchical complexity in networks representing human interactions, extending its utility to non-physical structures. Organizational hierarchies, such as corporate communication networks, are analyzed using Horton-Strahler indexing to uncover informal layers beneath formal charts; in one study of a company's email exchanges, branches were colored by Strahler order to reveal self-similar clustering, with higher orders indicating central decision pathways. Citation networks in academia employ Strahler numbers to assess knowledge flow depth, assigning orders to publications based on cited ancestors (order 1 for uncited works), with the maximum order reflecting influential "streams" of ideas; applied to high-energy physics papers (1992–2003), this revealed hierarchical diffusion patterns akin to tributary mergers. Social networks, including hunter-gatherer communities and virtual societies, exhibit fractal-like organization measurable by Strahler scaling; for example, in the online game Pardus, nested groups from individuals (order 1) to the full society (order 7) scale exponentially with a ratio of 4.3–4.4, demonstrating consistent multi-level embedding. Lindenmayer systems (L-systems), developed in the and extended in the for plant simulation, incorporate Strahler or Horton-Strahler branching rules to generate realistic growth patterns and approximate dimensions. These parametric models define iterative rules where branch orders increase upon symmetric mergers, mimicking natural asymmetry; seminal works used this to synthesize botanical trees, with Strahler analysis validating in veins and overall architecture. Recent ecological applications extend Strahler ordering to riverine food webs, modeling trophic hierarchies in metacommunities where branch orders represent predator-prey nesting, as noted in post-2021 studies on spatial patterns.

Computer Science Uses

In compiler theory, the Strahler number plays a key role in for evaluating arithmetic expressions represented as directed acyclic graphs (DAGs) or trees. The minimum number of registers required to evaluate an expression without spilling to memory equals the Strahler number of its syntax tree, ensuring optimal use of limited hardware resources during code generation. This equivalence arises because the Strahler numbering guides the evaluation order: subtrees with lower Strahler numbers are computed first, freeing registers for higher-complexity branches, as formalized in the Sethi-Ullman algorithm. For binary expression trees, such as those formed by operations like or (e.g., a complete of height hh has Strahler number h+1h + 1), a higher Strahler number directly implies greater demand for temporary storage, as more concurrent live values must be held during computation. In practice, this metric helps compilers determine if an expression can be evaluated in a single pass with available registers or requires optimization techniques like to reduce the effective Strahler number. Beyond compilers, the Strahler number bounds the rooted pathwidth of , providing insights into graph algorithms involving tree decompositions for problems like dynamic programming on trees. Specifically, the rooted pathwidth equals the Horton-Strahler number, enabling efficient approximations of decomposition widths in algorithms for testing or . In , it supports task scheduling for tree-structured dependencies, such as in expression evaluation or divide-and-conquer paradigms, where the number indicates the minimum processors needed to minimize synchronization overhead without excessive memory use.

Bifurcation Ratio

The bifurcation ratio, denoted RbR_b, is a key morphometric parameter in derived from Strahler stream ordering, defined as the ratio of the number of streams of order ii (NiN_i) to the number of streams of the next higher order i+1i+1 (Ni+1N_{i+1}), expressed as Rb=NiNi+1.R_b = \frac{N_i}{N_{i+1}}. This ratio is calculated for each consecutive pair of orders after completing the Strahler ordering process, which assigns hierarchical orders to based on their branching structure, and is then averaged across all orders in a to yield the mean bifurcation ratio Rb‾\overline{R_b}. The parameter quantifies the geometric progression of branching, reflecting how numbers decrease with increasing order in a network. In theoretical geometric trees, such as complete binary trees, RbR_b approaches 2, representing uniform bifurcation where each higher-order is formed by exactly two lower-order . In contrast, natural river networks exhibit RbR_b values typically ranging from 3 to 5, indicating irregularity and non-uniform branching influenced by geological and erosional processes; the Horton-Strahler ideal value hovers around 4, serving as a benchmark for mature, equilibrium drainage systems. Values outside this range, particularly deviations from 4, often signal external controls such as tectonic activity, where structural disturbances distort the drainage pattern and increase branching complexity. The bifurcation ratio has practical applications in hydrological modeling, particularly for flood prediction. Higher Rb‾\overline{R_b} values are linked to more peaked hydrographs with earlier peaks and steeper rising limbs, enhancing the potential for flash flooding due to concentrated runoff from irregular, structurally influenced networks. This metric thus aids in assessing basin susceptibility to rapid hydrological responses during intense storms.

Pathwidth

The pathwidth of a graph GG, denoted pw(G)\mathrm{pw}(G), is the minimum width over all path decompositions of GG, where a path decomposition consists of an ordered sequence of subsets of vertices called bags, such that: (i) every vertex of GG induces a consecutive subpath in the decomposition, (ii) every edge of GG has both endpoints in some common bag, and (iii) the width of the decomposition is one less than the size of its largest bag. This parameter relates to interval graph representations, as graphs of pathwidth at most kk are subgraphs of interval graphs whose maximum cliques have size at most k+1k+1. For , pathwidth is tightly connected to the Strahler number, serving as a graph-theoretic measure of hierarchical . Specifically, for an unrooted tree TT, if S(T)S(T) is defined as the minimum Strahler number over all possible rootings, then pw(T)−1≤S(T)≤2⋅pw(T)\mathrm{pw}(T) - 1 \leq S(T) \leq 2 \cdot \mathrm{pw}(T). In the rooted case, the Horton-Strahler number exactly equals the rooted pathwidth, which is the minimum pathwidth over all possible rootings and orientations toward the root. Both parameters quantify the "linear" of tree hierarchies by assessing the extent of branching versus path-like , with higher values indicating more balanced, deep ramifications that resist . Computing pathwidth is NP-hard for general graphs. However, for trees, it admits a linear-time based on dynamic programming over a postorder traversal, analogous to the bottom-up computation used for the Strahler number. In compiler optimization, particularly for expression trees, pathwidth yields tighter upper bounds on the minimum registers required compared to the Strahler number, especially for unrooted or cyclic extensions where the latter serves only as an approximation.

References

  1. https://agupubs.onlinelibrary.wiley.com/doi/10.1029/TR038i006p00913
  2. https://pubs.geoscienceworld.org/gsa/gsabulletin/article-abstract/56/3/275/4075/EROSIONAL-DEVELOPMENT-OF-STREAMS-AND-THEIR
  3. https://pro.arcgis.com/en/pro-app/latest/tool-reference/spatial-analyst/how-stream-order-works.htm
  4. https://projecteuclid.org/journals/electronic-journal-of-probability/volume-26/issue-none/The-HortonStrahler-number-of-conditioned-GaltonWatson-trees/10.1214/21-EJP678.full
  5. https://arxiv.org/pdf/2003.08627
  6. https://grass.osgeo.org/grass-stable/manuals/addons/v.stream.order.html
  7. https://tulip.labri.fr/publi_tulip/auberCMCSAT.pdf
  8. https://archive.model.in.tum.de/um/bibdb/esparza/latarevised16.pdf
  9. https://www.numdam.org/item/ITA_1996__30_5_443_0.pdf
  10. https://problab.ca/louigi/papers/rhs.pdf
  11. https://pubs.geoscienceworld.org/gsa/gsabulletin/article/56/3/275/4075/EROSIONAL-DEVELOPMENT-OF-STREAMS-AND-THEIR
  12. http://theory.stanford.edu/~megiddo/pdf/searchgraph.pdf
  13. https://compilers.iecc.com/comparch/article/08-05-013
  14. https://epubs.siam.org/doi/10.1137/0210004
  15. https://pro.arcgis.com/en/pro-app/latest/tool-reference/spatial-analyst/stream-order.htm
  16. https://doi.org/10.1016/0020-0190(95)00114-R
  17. https://arxiv.org/abs/2401.13771
  18. https://arxiv.org/abs/2307.05983
  19. https://arxiv.org/pdf/1511.01558
  20. https://onlinelibrary.wiley.com/doi/full/10.1111/j.1752-1688.2004.tb01057.x
  21. https://www.labri.fr/perso/auber/download/publi/auberICCVG2002.pdf
  22. https://www7.in.tum.de/~esparza/Talks/lata14.pdf
  23. https://arxiv.org/pdf/2307.05983
  24. https://arxiv.org/abs/2509.11384
  25. https://downloads.regulations.gov/OSM-2010-0018-10456/content.pdf
  26. https://www.tandfonline.com/doi/pdf/10.5268/IW-2.4.502
  27. https://www.sciencedirect.com/science/article/pii/S0034425719303797
  28. https://www.mdpi.com/2071-1050/13/24/13513
  29. https://pubs.geoscienceworld.org/gsa/gsabulletin/article/75/8/767/5795/EFFECT-OF-STREAM-ORDERING-TECHNIQUE-ON-HORTON-S
  30. https://www.journals.uchicago.edu/doi/10.1086/627137
  31. https://pro.arcgis.com/en/pro-app/3.4/tool-reference/spatial-analyst/how-stream-order-works.htm
  32. https://dl.acm.org/doi/10.1145/321607.321620
  33. https://link.springer.com/chapter/10.1007/978-3-319-04921-2_1
  34. https://link.springer.com/content/pdf/10.1007/978-3-0348-7915-6_21.pdf
  35. https://www.sciencedirect.com/science/article/pii/S0020019021001459
  36. https://pubs.usgs.gov/pp/0422g/report.pdf
  37. https://link.springer.com/article/10.1007/s13201-019-1055-0
  38. https://www.sciencedirect.com/science/article/abs/pii/S0020019021001459
Add your contribution
Related Hubs
User Avatar
No comments yet.