Pith. sign in

REVIEW 5 minor 159 references

Paths and Intersections: Minimum Realization of Okamura-Seymour Instances

T0 review · 0 major / 5 minor · reviewed 2026-07-12 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every Okamura–Seymour metric has a unique medial template whose arrangements give all minimum edge-count realizations, with lengths computable in polynomial time.

desk verdict Clean combinatorial solution: OS metrics determine a unique minimum-crossing medial template whose arrangements are exactly the min-edge realizations. read the letter →

arxiv 2607.02883 v1 pith:NQ7OE2E5 submitted 2026-07-03 cs.DS cs.CGmath.CO

Yu Chen , Pavlo Pylyavskyy , Zihan Tan This is my paper · ORCID
classification cs.DScs.CGmath.CO MSC 05C1205C8568R1090C35
keywords Okamura-SeymourinstancesminimumrealizationKalmansonmetricsmedialgraphsrepellingpairsshortest-pathY-Δtransformationsdisk-embedded
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

An Okamura–Seymour metric records shortest-path distances among terminals that sit on the boundary of a disk. The paper asks for the sparsest disk-embedded graphs that realize those distances exactly. It shows that the metric itself forces a single canonical matching of boundary points—the medial template—and that every minimum-edge realization is simply the primal graph of some arrangement of that template. The same template also supplies the exact minimum edge count. For any such graph the authors construct a good family of shortest paths and then recover nonnegative edge lengths that realize the metric. The argument treats the graph as a system of paths and their forced intersections, using repelling pairs as certificates that certain paths must stay vertex-disjoint.

What carries the argument

The medial template Φ(D): the unique perfect matching on alternating boundary points whose crossing numbers equal the corrected repelling cut sizes b_{x,y}. Arrangements of this template produce all minimum primal graphs, because crossings of medial chords become edges and the cut inequalities of Theorem 5 become tight.

What would settle it

Exhibit an OS metric D and a disk graph G that satisfies every chain inequality |M| ≤ |A| yet fails to admit any family of paths that are simultaneously vertex-disjoint on all repelling pairs and whose pairwise intersections are single subpaths; or produce two distinct templates both achieving the minimum crossing number for the same b_{x,y} numbers.

Watch

Extended reading notes

Core claim

For any OS metric D the cut numbers b_{x,y} derived from maximum repelling sets determine a unique medial template Φ(D). The graph structures of all minimum realizations of D are exactly the primal graphs of arrangements of Φ(D); each has precisely cr(Φ(D)) edges, and nonnegative lengths realizing D can be computed efficiently on every such graph.

Load-bearing premise

The claim rests on the equivalence that a graph admits a good shortest-path structure if and only if no repelling set of pairs crosses any chain more times than the chain’s length.

Editorial extensions

If this is right

  • All minimum OS realizations of a given metric share the same number of edges, equal to the crossing number of Φ(D).
  • The distinct embedded graphs realizing a metric with the fewest edges are related by Y–Δ moves that preserve the medial pairing.
  • Both the template and one concrete weighted realization can be recovered in polynomial time from the distance matrix alone.
  • Edge lengths realizing D on a fixed minimum graph need not be unique, even though the combinatorial structure is canonical.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same path-and-intersection viewpoint may yield minimum realizations for other planar or outerplanar metric families once suitable repelling certificates are defined.
  • Because the medial template is uniquely determined by local cut data, it supplies a compact certificate of structural complexity that could be used for metric compression or network tomography on disk-like topologies.
  • If the inductive construction of good paths can be derandomized or made fully combinatorial, the algorithm becomes a purely combinatorial reconstruction procedure with no numerical linear algebra.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper solves the minimum-edge realization problem for Okamura–Seymour metrics: given a Kalmanson metric D on a cyclically ordered terminal set T, recover all disk-embedded graphs with the fewest edges that realize D as shortest-path distances with the prescribed boundary order. The authors introduce repelling pairs (metric certificates of forced path separation), prove that an OS instance admits a D-good shortest-path structure if and only if every repelling set M and every chain A satisfy |M| ≤ |A| (Theorem 5), and show that the resulting cut numbers a_{x,y} (after endpoint correction to b_{x,y}) determine a unique medial template Φ(D) via circular inversion (Lemma 13). Minimum realizations are exactly the primal graphs of arrangements of Φ(D) (Lemma 16), each having cr(Φ(D)) edges; for any such graph, nonnegative edge lengths realizing D can be computed efficiently (Theorem 19). The development is paralleled with the inverse problem for electrical networks (Table 1).

Significance. The result gives a complete structural and algorithmic solution for minimum OS realizations: a canonical template is recovered from D alone, all minimal embedded graphs are identified as arrangements of that template, and realizing lengths are efficiently obtainable. The paths-and-intersections viewpoint, the characterization via repelling pairs and chains, and the exact parallel with critical electrical networks are of independent interest for metric graph theory and planar algorithms. The claims are constructive and the non-uniqueness of lengths is correctly exhibited (Appendix A). If the polynomial-time claims hold, the paper supplies a clean, usable compression of OS metrics.

minor comments (5)
  1. Theorem 1 and the opening of Section 4 assert that the template (hence all a_{x,y}/b_{x,y}) can be computed in polynomial time, yet no explicit procedure is given for evaluating the maximum size of a mutually repelling set of pairs that cross a given cut. While Observation 2 and the ordered-exchange arguments of Lemma 10 suggest a greedy or DP algorithm exists, a short paragraph or reference confirming poly-time computability would make the efficiency claim self-contained.
  2. Figure 1 caption refers to “path Π[i+1, j+1] (red)”; the surrounding text and construction use Π[i+1, j−1]. Correct the index.
  3. The concurrent preprint [CT26] is cited for Lemma 3 and for the uncrossing lemma used in Theorem 15. A one-sentence statement of the precise statements borrowed would help readers who do not yet have access to that manuscript.
  4. In the definition of chains (Definition 4) the length |A| counts only vertices; a parenthetical reminder that peripheral regions contribute zero would reduce the chance of off-by-one confusion when the endpoint correction for b_{x,y} is introduced.
  5. Table 1 is helpful; adding a one-line pointer in the caption to the precise theorems that justify each row of the “Distance realization” column would improve readability.

Circularity Check

2 steps flagged · score 2.0 of 10

Minor self-citations to concurrent work supply two auxiliary black-box lemmas; the template extraction from cut numbers and the chain-characterization of good structures are derived independently inside the paper.

  1. self citation load bearing [Lemma 14 (Section 4.3) and its invocation in Theorem 15 / Lemma 16]
    "Lemma 14. If Φ ⪰ Φ′, then Φ → Φ′. The following lemma was proved in [CT26]."

    The claim that Φ(D) is the unique minimum-crossing feasible template (Theorem 15), and therefore that every minimum realization graph is an arrangement of exactly this template (Lemma 16), rests on the uncrossing implication imported from the concurrent self-citation. The implication itself is a parameter-free combinatorial fact about chord diagrams and does not presuppose the OS-metric results, so the dependence is mild rather than definitional.

  2. self citation load bearing [Lemma 3 (Section 2) and its use in Lemma 16 / Theorem 19]
    "Lemma 3. An OS instance (G, T) realizes a metric D on T iff it admits a good shortest path structure. Moreover, such an edge-length function in G, if it exists, can be found efficiently. The following lemma is proved in [CT26]."

    The direction “realizes ⇒ admits good SPS” is invoked to conclude that every realizing graph satisfies the chain lower bounds a_{x,y}, and the constructive length-finding algorithm is used to finish Theorem 19. Both pieces come from the concurrent self-citation. The paper independently proves the converse direction via its own inductive construction (Theorem 5), so the self-cite supplies only one half of the equivalence and the algorithmic recovery of lengths.

full rationale

The derivation begins from the metric D, defines repelling pairs and a_{x,y} by explicit maximization, corrects to b_{x,y}, and obtains the unique template Φ(D) by the linear inversion formula (4) together with the parity/uniqueness argument of Lemma 12 (all proved in-place). Theorem 5 constructs a good shortest-path structure from the chain inequalities by an inductive path-building argument that is self-contained. Arrangements of Φ(D) are then shown to satisfy those inequalities, hence to realize D once lengths are assigned, and to achieve the edge lower bound. The only external load-bearing ingredients are Lemma 3 (realizes ⇔ good SPS + length recovery) and Lemma 14 (uncrossing implication) from the authors’ concurrent paper [CT26]. Both are purely combinatorial statements independent of the target OS-metric claims; they function as black boxes and do not feed the definition of Φ(D) or the chain inequalities back into themselves. Consequently there is no self-definitional loop, no fitted-parameter-as-prediction, and no uniqueness theorem that merely renames the present result. The circularity score is therefore low.

Assumptions & free parameters 0 free parameters · 3 assumptions · 3 invented entities

The paper works entirely inside classical planar graph theory and metric geometry. No free parameters are fitted. The only non-standard objects are definitional (repelling pairs, chains, the derived template Φ(D)); they are introduced with explicit combinatorial definitions and used constructively. Background facts (Kalmanson characterization of OS metrics, medial-graph duality, Y-Δ distance preservation) are standard and cited.

assumptions (3)
  • domain assumption A metric on a cyclically ordered terminal set is realizable by an OS instance if and only if it satisfies the Kalmanson four-point inequalities.
    Invoked from the first paragraph of Section 1 and used as the definition of an OS metric; classical result of Hurkens-Lovász-Schrijver-Tardos / Chepoi-Osajda.
  • domain assumption An OS instance realizes D if and only if it admits a D-good shortest-path structure (paths for every terminal pair that intersect in subpaths and are vertex-disjoint for repelling pairs).
    Lemma 3, cited from the authors' concurrent paper [CT26]; treated as a black-box equivalence throughout Sections 3-4.
  • standard math Y-Δ transformations preserve all terminal-to-terminal distances when the three new lengths are the standard non-negative combinations of the old ones.
    Recalled in Section 4.1; classical and used only to relate different arrangements of the same template.
invented entities (3)
  • repelling pairs / repelling sets
    purpose: Metric certificates that force shortest paths to be vertex-disjoint; supply the lower bounds a_{x,y} on chain lengths.
    Defined in Section 2 from the strict four-point inequality; the entire lower-bound theory rests on them. Independent evidence is internal (they are purely combinatorial).
  • medial template Φ(D)
    purpose: The unique perfect matching on the doubled boundary points whose cut distances equal the corrected repelling numbers b_{x,y}; its arrangements are exactly the minimum realizations.
    Constructed in Lemma 13 by circular inversion of the b-matrix; uniqueness and minimality of crossings are the main structural theorems. No external physical or experimental handle is claimed.
  • chains (vertex-region sequences from boundary to boundary)
    purpose: Discrete objects that count the number of primal vertices a set of paths must cross; convert repelling lower bounds into medial-chord lower bounds.
    Defined in Section 2; used as the combinatorial dual of medial cut distances. Purely definitional.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Paths and Intersections: Minimum Realization of Okamura-Seymour Instances." pith.science (2026). https://pith.science/paper/NQ7OE2E5

@misc{pith2026260702883,
  author       = {Pith},
  title        = {Pith review of: Paths and Intersections: Minimum Realization of Okamura-Seymour Instances},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NQ7OE2E5}},
  note         = {Machine review of arXiv:2607.02883}
}
abstract

We study the inverse problem for shortest-path metrics of Okamura-Seymour (OS) instances. Given an OS metric $D$ on a cyclically ordered terminal set $T$, the goal is to find minimum realizations of $D$, where minimum means having the fewest edges among all disk-embedded realizations with the prescribed terminal order. We show that $D$ determines a canonical medial graph template and every minimum realization is the primal graph of an arrangement of this template. Consequently, the underlying embedded graphs of minimum realizations of $D$ can be recovered, and for each such graph one can efficiently compute edge lengths realizing $D$. Our algorithm follows a recent approach of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

Figures

Figures reproduced from arXiv: 2607.02883 by the authors.

Figure 1
Figure 1. Path Π[i, j] in Case 1 (purple dashed line on the left): the other side of the the strip (light green area) supported by path Π[i+ 1, j + 1] (red), and the chain from vertex x built inductively (gray sequence on the right). gives a chain, and the singleton set M = {(i, j)} satisfies the conditions in the claim with this chain. Consider now a general pair i, j with j ≥ i + 2. We distinguish between the following two … view at source ↗
Figure 2
Figure 2. Path Π[i, j] (black), chain A (gray), path Π[j, i] (red) and chain A′ (pink). In the case where there is no bad pair, we construct a good shortest path structure as follows. If n is odd, then for every pair i, j of terminals, one of the two segments ∂[i, j], ∂[j, i] contains strictly fewer terminals than the other, say ∂[i, j], and we let Pi,j = Π[i, j]. If n is even, then we arbitrarily pick a non-terminal point x … view at source ↗
Figure 3
Figure 3. Left: the primal graph. Terminals are shown in blue (the other reference points in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Minimum realizations of metric D: green edge weights are not unique. Consider a metric D on 8 points {t1, . . . , t8} defined as follows (indices modulo 8). • for each i, D(ti , ti+1) = 1, D(ti , ti+2) = 2, and D(ti , ti+3) = 3; and • D(t1, t5) = D(t3, t7) = 3, and D(t…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

159 extracted references · 18 linked inside Pith

  1. [1]

    arXiv preprint arXiv:2606.25827 , year=

    Paths and Intersections: Recognizing Outerplanar Metrics , author=. arXiv preprint arXiv:2606.25827 , year=

    arXiv

  2. [2]

    Louis and Yau, Stephen S

    Hakimi, S. Louis and Yau, Stephen S. , title =. Quarterly of Applied Mathematics , volume =. 1965 , doi =

    1965

  3. [3]

    Goldman, A. J. , title =. Journal of Research of the National Bureau of Standards, Section B: Mathematics and Mathematical Physics , volume =. 1966 , doi =

    1966

  4. [4]

    On Optimal Realizations of Finite Metric Spaces by Graphs , journal =

    Alth. On Optimal Realizations of Finite Metric Spaces by Graphs , journal =. 1988 , doi =

    1988

  5. [5]

    SIAM Journal on Discrete Mathematics , volume =

    Winkler, Peter , title =. SIAM Journal on Discrete Mathematics , volume =. 1988 , doi =

    1988

  6. [6]

    Annual Symposium on Theoretical Aspects of Computer Science , pages=

    Representing graph metrics with fewest edges , author=. Annual Symposium on Theoretical Aspects of Computer Science , pages=. 2003 , organization=

    2003

  7. [7]

    arXiv preprint arXiv:2507.09620 , year=

    Paths and Intersections: Exact Emulators for Planar Graphs , author=. arXiv preprint arXiv:2507.09620 , year=

    arXiv

  8. [8]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

    2025

Show all 159 references
  1. [9]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Planar diameter via metric compression , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

  2. [10]

    arXiv preprint arXiv:1807.01478 , year=

    Near-optimal distance emulator for planar graphs , author=. arXiv preprint arXiv:1807.01478 , year=

    arXiv

  3. [11]

    1972 , publisher=

    Multicommodity Maximum Flow in Planar Networks; the D-algorithm Approach , author=. 1972 , publisher=

    1972

  4. [12]

    Quarterly of applied mathematics , volume=

    The distance matrix of a graph and its tree realization , author=. Quarterly of applied mathematics , volume=

  5. [13]

    Discrete mathematics , volume=

    Trees related to realizations of distance matrices , author=. Discrete mathematics , volume=. 1998 , publisher=

    1998

  6. [14]

    Linear algebra and its applications , volume=

    Distance spectra of graphs: A survey , author=. Linear algebra and its applications , volume=. 2014 , publisher=

    2014

  7. [15]

    Algorithmica , volume=

    Composed degree-distance realizations of graphs , author=. Algorithmica , volume=. 2023 , publisher=

    2023

  8. [16]

    Discrete mathematics , volume=

    GRAPH REALIZATIONS , author=. Discrete mathematics , volume=

  9. [17]

    Linear Algebra and Its Applications , volume=

    Submatrices of non-tree-realizable distance matrices , author=. Linear Algebra and Its Applications , volume=. 1982 , publisher=

    1982

  10. [18]

    SIAM Journal on Discrete Mathematics , volume=

    Recognition of tree metrics , author=. SIAM Journal on Discrete Mathematics , volume=. 1990 , publisher=

    1990

  11. [19]

    47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) , year=

    Graph realization of distance sets , author=. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) , year=

    2022

  12. [20]

    Information Processing Letters , volume=

    On max-flow min-cut and integral flow properties for multicommodity flows in directed networks , author=. Information Processing Letters , volume=. 1989 , publisher=

    1989

  13. [21]

    arXiv preprint arXiv:2202.05127 , year=

    Improved Compression of the Okamura-Seymour Metric , author=. arXiv preprint arXiv:2202.05127 , year=

    arXiv

  14. [22]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    On the structure of unique shortest paths in graphs , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  15. [23]

    Journal of Graph Theory , volume=

    Irreducible nonmetrizable path systems in graphs , author=. Journal of Graph Theory , volume=. 2023 , publisher=

    2023

  16. [24]

    Discrete & Computational Geometry , volume=

    Geodesic geometry on graphs , author=. Discrete & Computational Geometry , volume=. 2022 , publisher=

    2022

  17. [25]

    arXiv preprint arXiv:2211.07042 , year=

    A local-to-global theorem for congested shortest paths , author=. arXiv preprint arXiv:2211.07042 , year=

    arXiv

  18. [26]

    Combinatorica , volume=

    The geometry of graphs and some of its algorithmic applications , author=. Combinatorica , volume=. 1995 , publisher=

    1995

  19. [27]

    Journal of the ACM (JACM) , volume=

    Polynomial flow-cut gaps and hardness of directed cut problems , author=. Journal of the ACM (JACM) , volume=. 2009 , publisher=

    2009

  20. [28]

    Advances in Mathematics , volume=

    Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces , author=. Advances in Mathematics , volume=. 1984 , publisher=

    1984

  21. [29]

    Journal of combinatorial theory , volume=

    A note on the tree realizability of a distance matrix , author=. Journal of combinatorial theory , volume=. 1969 , publisher=

    1969

  22. [30]

    A note on the metric properties of trees , author=. J. Combin. Theory Ser. B , volume=

  23. [31]

    Information Processing Letters , volume=

    Recognizing and realizing cactus metrics , author=. Information Processing Letters , volume=. 2020 , publisher=

    2020

  24. [32]

    2015 , publisher=

    Graph-theoretical matrices in chemistry , author=. 2015 , publisher=

    2015

  25. [33]

    Journal of the Royal Statistical Society: Series A (General) , volume=

    A review of hierarchical classification , author=. Journal of the Royal Statistical Society: Series A (General) , volume=. 1987 , publisher=

    1987

  26. [34]

    Journal of Computer and System Sciences , volume=

    Distance realization problems with applications to internet tomography , author=. Journal of Computer and System Sciences , volume=. 2001 , publisher=

    2001

  27. [35]

    2012 , publisher=

    Basic phylogenetic combinatorics , author=. 2012 , publisher=

    2012

  28. [36]

    Quarterly of applied mathematics , volume=

    Distance matrix of a graph and its realizability , author=. Quarterly of applied mathematics , volume=

  29. [37]

    Proceedings of Colloquia Mathematica Societatis Janos Bolyai , volume=

    How to tidy up your set-system , author=. Proceedings of Colloquia Mathematica Societatis Janos Bolyai , volume=

  30. [38]

    A Fourier-f

    Farkas, Gyula , journal=. A Fourier-f

  31. [39]

    arXiv preprint arXiv:1711.01370 , year=

    On constant multi-commodity flow-cut gaps for directed minor-free graphs , author=. arXiv preprint arXiv:1711.01370 , year=

    arXiv

  32. [40]

    2003 , publisher=

    Combinatorial optimization: polyhedra and efficiency , author=. 2003 , publisher=

    2003

  33. [41]

    Planar Emulators for Monge Matrices , booktitle =

    Hsien. Planar Emulators for Monge Matrices , booktitle =

  34. [42]

    2020 , url =

    Gramoz Goranci and Monika Henzinger and Pan Peng , title =. 2020 , url =

    2020

  35. [43]

    SIAM Journal on Discrete Mathematics , volume=

    Preserving terminal distances using minors , author=. SIAM Journal on Discrete Mathematics , volume=. 2014 , publisher=

    2014

  36. [44]

    Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Almost-linear -emulators for planar graphs , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

  37. [45]

    arXiv preprint arXiv:2310.07857 , year=

    On (1+eps) -Approximate Flow Sparsifiers , author=. arXiv preprint arXiv:2310.07857 , year=

    arXiv

  38. [46]

    Discrete Mathematics , volume=

    Realizing symmetric set functions as hypergraph cut capacity , author=. Discrete Mathematics , volume=. 2016 , publisher=

    2016

  39. [47]

    Discrete Mathematics , volume=

    Realization of set functions as cut functions of graphs and hypergraphs , author=. Discrete Mathematics , volume=. 2001 , publisher=

    2001

  40. [48]

    , author=

    Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. , author=. Soda , volume=. 1993 , organization=

    1993

  41. [49]

    Shiva Chaudhuri and K. V. Subrahmanyam and Frank Wagner and Christos D. Zaroliagis , title =. Algorithmica , volume =. 2000 , url =

    2000

  42. [50]

    Combinatorica , volume=

    A factor 2 approximation algorithm for the generalized Steiner network problem , author=. Combinatorica , volume=. 2001 , publisher=

    2001

  43. [51]

    2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=

    Representative sets and irrelevant vertices: New tools for kernelization , author=. 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages=. 2012 , organization=

    2012

  44. [52]

    Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Vertex sparsification for edge connectivity , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  45. [53]

    arXiv preprint arXiv:2011.15101 , year=

    Vertex sparsification for edge connectivity in polynomial time , author=. arXiv preprint arXiv:2011.15101 , year=

    2011 arXiv

  46. [54]

    2001 , publisher=

    Hereditarily optimal realizations: Why are they relevant in phylogenetic analysis, and how does one compute them , author=. 2001 , publisher=

    2001

  47. [55]

    Annals of Combinatorics , volume=

    Hereditarily optimal realizations of consistent metrics , author=. Annals of Combinatorics , volume=. 2006 , publisher=

    2006

  48. [56]

    Discrete & Computational Geometry , volume=

    Concerning the relationship between realizations and tight spans of finite metrics , author=. Discrete & Computational Geometry , volume=. 2007 , publisher=

    2007

  49. [57]

    the electronic journal of combinatorics , volume=

    Characterizing cell-decomposable metrics , author=. the electronic journal of combinatorics , volume=

  50. [58]

    Discrete Applied Mathematics , volume=

    Optimal realizations and the block decomposition of a finite metric space , author=. Discrete Applied Mathematics , volume=. 2021 , publisher=

    2021

  51. [59]

    European Journal of Combinatorics , volume=

    T-theory: an overview , author=. European Journal of Combinatorics , volume=. 1996 , publisher=

    1996

  52. [60]

    Computer Science Review , volume=

    Graph spanners: A tutorial review , author=. Computer Science Review , volume=. 2020 , publisher=

    2020

  53. [61]

    Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    The expander hierarchy and its applications to dynamic graph algorithms , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

    2021

  54. [62]

    under submission , year=

    On (1 + eps)-Approximate Flow Sparsifiers , author=. under submission , year=

  55. [63]

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Fast dynamic cuts, distances and effective resistances via vertex sparsifiers , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

    2020

  56. [64]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Fully dynamic spectral vertex sparsifiers and applications , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

  57. [65]

    Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25--26, 2016, Revised Selected Papers , pages=

    Vertex sparsification in trees , author=. Approximation and Online Algorithms: 14th International Workshop, WAOA 2016, Aarhus, Denmark, August 25--26, 2016, Revised Selected Papers , pages=. 2017 , organization=

    2016

  58. [66]

    European Journal of Combinatorics , volume=

    Optimal realizations of generic five-point metrics , author=. European Journal of Combinatorics , volume=. 2009 , publisher=

    2009

  59. [67]

    arXiv preprint arXiv:2102.05077 , year=

    The Multiplicative Version of Azuma's Inequality, with an Application to Contention Analysis , author=. arXiv preprint arXiv:2102.05077 , year=

    arXiv

  60. [68]

    Journal of Computer and System Sciences , volume=

    Characterizing multiterminal flow networks and computing flows in networks of small treewidth , author=. Journal of Computer and System Sciences , volume=. 1998 , publisher=

    1998

  61. [69]

    On the evolution of random graphs , author=. Publ. Math. Inst. Hung. Acad. Sci , volume=

  62. [70]

    Information Processing Letters , volume=

    On mimicking networks representing minimum terminal cuts , author=. Information Processing Letters , volume=. 2014 , publisher=

    2014

  63. [71]

    arXiv preprint arXiv:1706.06086 , year=

    An exponential lower bound for cut sparsifiers in planar graphs , author=. arXiv preprint arXiv:1706.06086 , year=

    arXiv

  64. [72]

    Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Mimicking networks and succinct representations of terminal cuts , author=. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2013 , organization=

    2013

  65. [73]

    arXiv preprint arXiv:1702.01136 , year=

    Improved guarantees for vertex sparsification in planar graphs , author=. arXiv preprint arXiv:1702.01136 , year=

    arXiv

  66. [74]

    arXiv preprint arXiv:1702.05951 , year=

    Refined vertex sparsifiers of planar graphs , author=. arXiv preprint arXiv:1702.05951 , year=

    arXiv

  67. [75]

    , author=

    Delta-Wye-Delta transformations: algorithms and applications. , author=

  68. [76]

    Foundations of Computer Science, 2009

    Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size , author=. Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on , pages=. 2009 , organization=

    2009

  69. [77]

    SIAM Journal on Computing , volume=

    Vertex sparsification and oblivious reductions , author=. SIAM Journal on Computing , volume=. 2013 , publisher=

    2013

  70. [78]

    Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

    An improved approximation algorithm for the 0-extension problem , author=. Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2003 , organization=

    2003

  71. [79]

    Journal of the ACM (JACM) , volume=

    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms , author=. Journal of the ACM (JACM) , volume=. 1999 , publisher=

    1999

  72. [80]

    Flows, Cuts and Integral Routing in Graphs - an Approximation Algorithmist's Perspective , author=. Proc. of the International Congress of Mathematicians , volume=. 2016 , publisher=

    2016

  73. [81]

    Foundations of Computer Science, 2002

    Minimizing congestion in general networks , author=. Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on , pages=. 2002 , organization=

    2002

  74. [82]

    Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    Extensions and limits to vertex sparsification , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=. 2010 , organization=

    2010

  75. [83]

    Journal of the ACM (JACM) , volume=

    Expander flows, geometric embeddings and graph partitioning , author=. Journal of the ACM (JACM) , volume=. 2009 , publisher=

    2009

  76. [84]

    Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages=

    Vertex sparsifiers and abstract rounding algorithms , author=. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages=. 2010 , organization=

    2010

  77. [85]

    Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages=

    Metric extension operators, vertex sparsifiers and lipschitz extendability , author=. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages=. 2010 , organization=

    2010

  78. [86]

    SIAM Journal on Computing , volume=

    Vertex sparsifiers: New results from old techniques , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

  79. [87]

    arXiv preprint arXiv:0907.3631 , year=

    Interchanging distance and capacity in probabilistic mappings , author=. arXiv preprint arXiv:0907.3631 , year=

    arXiv

  80. [88]

    Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Steiner points in tree metrics don't (really) help , author=. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2001 , organization=

    2001

  81. [89]

    Approximation, Randomization, and Combinatorial Optimization

    A tight lower bound for the steiner point removal problem on trees , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pages=. 2006 , publisher=

    2006

  82. [90]

    Unpublished Manuscript, available from http://www

    Steiner point removal in graph metrics , author=. Unpublished Manuscript, available from http://www. math. ucdavis. edu/\

  83. [91]

    SIAM Journal on Discrete Mathematics , volume=

    Sparse sourcewise and pairwise distance preservers , author=. SIAM Journal on Discrete Mathematics , volume=. 2006 , publisher=

    2006

  84. [92]

    SIAM Journal on Computing , volume=

    All-pairs almost shortest paths , author=. SIAM Journal on Computing , volume=. 2000 , publisher=

    2000

  85. [93]

    Foundations of Computer Science, 2006

    Lower bounds for additive spanners, emulators, and more , author=. Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on , pages=. 2006 , organization=

    2006

  86. [94]

    SIAM Journal on Computing , volume=

    Cutting corners cheaply, or how to remove steiner points , author=. SIAM Journal on Computing , volume=. 2015 , publisher=

    2015

  87. [95]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Steiner point removal: distant terminals don't (really) bother , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  88. [96]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Steiner point removal with distortion O (log k) , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  89. [97]

    arXiv preprint arXiv:1809.00942 , year=

    Noisy Voronoi: a Simple Framework for Terminal-Clustering Problems , author=. arXiv preprint arXiv:1809.00942 , year=

    arXiv

  90. [98]

    Preprint , year=

    Metric decomposition, smooth measures, and clustering , author=. Preprint , year=

  91. [99]

    arXiv preprint arXiv:1604.08342 , year=

    Graph minors for preserving terminal distances approximately-lower and upper bounds , author=. arXiv preprint arXiv:1604.08342 , year=

    arXiv

  92. [100]

    Discrete & Computational Geometry , volume=

    On sparse spanners of weighted graphs , author=. Discrete & Computational Geometry , volume=. 1993 , publisher=

    1993

  93. [101]

    Combinatorica , volume=

    Cuts, trees and ? 1-embeddings of graphs , author=. Combinatorica , volume=. 2004 , publisher=

    2004

  94. [102]

    Combinatorica , volume=

    Pathwidth, trees, and random embeddings , author=. Combinatorica , volume=. 2013 , publisher=

    2013

  95. [103]

    Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

    On the geometry of graphs with a forbidden minor , author=. Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=. 2009 , organization=

    2009

  96. [104]

    SIAM Journal on Discrete Mathematics , volume=

    Embedding k-outerplanar graphs into l1 , author=. SIAM Journal on Discrete Mathematics , volume=. 2006 , publisher=

    2006

  97. [105]

    Journal of the ACM (JACM) , volume=

    Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields , author=. Journal of the ACM (JACM) , volume=. 2002 , publisher=

    2002

  98. [106]

    SIAM Journal on Computing , volume=

    The complexity of multiterminal cuts , author=. SIAM Journal on Computing , volume=. 1994 , publisher=

    1994

  99. [107]

    Journal of Computer and System Sciences , volume=

    An improved approximation algorithm for multiway cut , author=. Journal of Computer and System Sciences , volume=. 2000 , publisher=

    2000

  100. [108]

    Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=

    SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling , author=. Proceedings of the fortieth annual ACM symposium on Theory of computing , pages=. 2008 , organization=

    2008

  101. [109]

    European Journal of Combinatorics , volume=

    Minimum 0-extensions of graph metrics , author=. European Journal of Combinatorics , volume=. 1998 , publisher=

    1998

  102. [110]

    SIAM Journal on Computing , volume=

    Approximation algorithms for the 0-extension problem , author=. SIAM Journal on Computing , volume=. 2005 , publisher=

    2005

  103. [111]

    Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Approximate classification via earthmover metrics , author=. Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2004 , organization=

    2004

  104. [112]

    SIAM Journal on Computing , volume=

    On earthmover distance, metric labeling, and 0-extension , author=. SIAM Journal on Computing , volume=. 2009 , publisher=

    2009

  105. [113]

    Proceedings of the twenty-third annual symposium on Computational geometry , pages=

    Probabilistic embeddings of bounded genus graphs into planar graphs , author=. Proceedings of the twenty-third annual symposium on Computational geometry , pages=. 2007 , organization=

    2007

  106. [114]

    Computational Geometry , volume=

    Randomly removing g handles at once , author=. Computational Geometry , volume=. 2010 , publisher=

    2010

  107. [115]

    Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages=

    Genus and the geometry of the cut graph , author=. Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pages=. 2010 , organization=

    2010

  108. [116]

    Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages=

    Optimal stochastic planarization , author=. Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on , pages=. 2010 , organization=

    2010

  109. [117]

    Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Flow-cut gaps and face covers in planar graphs , author=. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

    2019

  110. [118]

    Journal of Combinatorial Theory, Series B , volume=

    Flow-cut gaps for integer and fractional multiflows , author=. Journal of Combinatorial Theory, Series B , volume=. 2013 , publisher=

    2013

  111. [119]

    Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

    Metric embedding via shortest path decompositions , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=. 2018 , organization=

    2018

  112. [120]

    Israel Journal of Mathematics , volume=

    On Lipschitz embedding of finite metric spaces in Hilbert space , author=. Israel Journal of Mathematics , volume=. 1985 , publisher=

    1985

  113. [121]

    Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

    Advances in metric embedding theory , author=. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=. 2006 , organization=

    2006

  114. [122]

    Foundations of Computer Science, 2004

    Measured descent: A new embedding method for finite metrics , author=. Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on , pages=. 2004 , organization=

    2004

  115. [123]

    Geometric & Functional Analysis GAFA , volume=

    Embedding the diamond graph in L p and dimension reduction in L 1 , author=. Geometric & Functional Analysis GAFA , volume=. 2004 , publisher=

    2004

  116. [124]

    Canadian Journal of Mathematics , volume=

    Graph theory and probability , author=. Canadian Journal of Mathematics , volume=. 1959 , publisher=

    1959

  117. [125]

    2009 , publisher=

    Concentration of measure for the analysis of randomized algorithms , author=. 2009 , publisher=

    2009

  118. [126]

    Inventiones mathematicae , volume=

    Expansion of random graphs: New proofs, new results , author=. Inventiones mathematicae , volume=. 2015 , publisher=

    2015

  119. [127]

    Random Structures & Algorithms , volume=

    Hamilton cycles in the union of random permutations , author=. Random Structures & Algorithms , volume=. 2001 , publisher=

    2001

  120. [128]

    , author=

    Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. , author=. SODA , volume=

  121. [129]

    Mathematics of Operations Research , volume=

    Random sampling in cut, flow, and network design problems , author=. Mathematics of Operations Research , volume=. 1999 , publisher=

    1999

  122. [130]

    Approximate s-t min-cuts in

    Bencz. Approximate s-t min-cuts in. Proc. 28th ACM Symposium on Theory of Computing, 1996 , year=

    1996

  123. [131]

    arXiv preprint arXiv:1005.0265 , year=

    Graph sparsification by edge-connectivity and random spanning trees , author=. arXiv preprint arXiv:1005.0265 , year=

    arXiv

  124. [132]

    SIAM Journal on Computing , volume=

    Graph sparsification by effective resistances , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  125. [133]

    SIAM Journal on Computing , volume=

    Twice-ramanujan sparsifiers , author=. SIAM Journal on Computing , volume=. 2012 , publisher=

    2012

  126. [134]

    The metric relaxation for 0-extension admits an ( ^

    Schwartz, Roy and Tur, Nitzan , booktitle=. The metric relaxation for 0-extension admits an ( ^

  127. [135]

    Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

    On earthmover distance, metric labeling, and 0-extension , author=. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , pages=

  128. [136]

    SIAM Journal on Computing , volume=

    The hardness of metric labeling , author=. SIAM Journal on Computing , volume=. 2007 , publisher=

    2007

  129. [137]

    SIAM Journal on Discrete Mathematics , volume=

    A linear programming formulation and approximation algorithms for the metric labeling problem , author=. SIAM Journal on Discrete Mathematics , volume=. 2004 , publisher=

    2004

  130. [138]

    Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Approximate classification via earthmover metrics , author=. Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms , pages=

  131. [139]

    Mathematical Programming , volume=

    Improving the integrality gap for multiway cut , author=. Mathematical Programming , volume=. 2020 , publisher=

    2020

  132. [140]

    Proceedings of the forty-second ACM symposium on Theory of computing , pages=

    Extensions and limits to vertex sparsification , author=. Proceedings of the forty-second ACM symposium on Theory of computing , pages=

  133. [141]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Exact Flow Sparsification Requires Unbounded Size , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  134. [142]

    Towards (1+

    Andoni, Alexandr and Gupta, Anupam and Krauthgamer, Robert , booktitle=. Towards (1+. 2014 , organization=

    2014

  135. [143]

    Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

    On vertex sparsifiers with Steiner nodes , author=. Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

  136. [144]

    Proceedings of the twenty-eighth annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Simplex transformations and the multiway cut problem , author=. Proceedings of the twenty-eighth annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2017 , organization=

    2017

  137. [145]

    Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

    Simplex partitioning via exponential clocks and the multiway cut problem , author=. Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

  138. [146]

    A lower bound of

    Freund, Ari and Karloff, Howard , journal=. A lower bound of. 2000 , publisher=

    2000

  139. [147]

    Proceedings of the thirtieth annual ACM symposium on Theory of computing , pages=

    An improved approximation algorithm for multiway cut , author=. Proceedings of the thirtieth annual ACM symposium on Theory of computing , pages=

  140. [148]

    An improved integrality gap for the C

    Angelidakis, Haris and Makarychev, Yury and Manurangsi, Pasin , booktitle=. An improved integrality gap for the C. 2017 , organization=

    2017

  141. [149]

    , author=

    Planar Emulators for Monge Matrices. , author=. CCCG , pages=

  142. [150]

    Journal of Combinatorial Theory, Series B , volume=

    Multicommodity flows in planar graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 1981 , publisher=

    1981

  143. [151]

    Andoni, Alexandr and Gupta, Anupam and Krauthgamer, Robert , booktitle=. Towards. 2014 , organization=

    2014

  144. [152]

    de Verdiere, Yves Colin and Gitler, Isidoro and Vertigan, Dirk , journal=. R. 1996 , publisher=

    1996

  145. [153]

    Linear algebra and its applications , volume=

    Circular planar graphs and resistor networks , author=. Linear algebra and its applications , volume=. 1998 , publisher=

    1998

  146. [154]

    Transactions of the American Mathematical Society , volume=

    Boundary partitions in trees and dimers , author=. Transactions of the American Mathematical Society , volume=

  147. [155]

    arXiv preprint arXiv:0811.1766 , year=

    Combinatorics of tripartite boundary connections for trees and dimers , author=. arXiv preprint arXiv:0811.1766 , year=

    arXiv

  148. [156]

    Canadian Journal of Mathematics , volume=

    Edgeconvex circuits and the traveling salesman problem , author=. Canadian Journal of Mathematics , volume=. 1975 , publisher=

    1975

  149. [157]

    Advances in mathematics , volume=

    A canonical decomposition theory for metrics on a finite set , author=. Advances in mathematics , volume=. 1992 , publisher=

    1992

  150. [158]

    SIAM Journal on Applied Algebra and Geometry , volume=

    Circular planar electrical networks, split systems, and phylogenetic networks , author=. SIAM Journal on Applied Algebra and Geometry , volume=. 2023 , publisher=

    2023

  151. [159]

    arXiv preprint arXiv:2501.01383 , year=

    Electrical networks and data analysis in phylogenetics , author=. arXiv preprint arXiv:2501.01383 , year=

    arXiv

Pith tools

Reviewed July 12, 2026 · model on record in the stance chip above.