Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

Paths and Intersections: Exact Emulators for Planar Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Every edge-weighted planar graph with $k$ terminals lying on $f$ faces has an exact planar emulator with $O(f^2 k^2)$ vertices.

desk verdict The f-face emulator result is a natural target and the skeleton construction is genuinely new, but the Wye-Delta min-cut calculation in Observation 28 is wrong, and that error sinks the flow-morphing proof of the edge-weight lemma. read the letter →

arxiv 2507.09620 v1 pith:PHUN6HXI submitted 2025-07-13 cs.DS math.CO

George Z. Li , Zihan Tan , Tianyi Zhang This is my paper · ORCID
classification cs.DSmath.CO MSC 05C1005C1205C8568R10
keywords planargraphsvertexsparsificationdistanceemulatorsexactcriticalpathscanonicallinearprogrammingfeasibilityWye-Deltatransformation
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

This paper aims to prove that an edge-weighted planar graph with $k$ terminals all lying on the boundaries of $f$ faces can be compressed to a planar graph on $O(f^2 k^2)$ vertices that exactly preserves every terminal-to-terminal distance. The result would generalize the known $O(k^2)$ construction for terminals on one face and the $O(k^4)$ construction for the general case, suggesting that the number of faces is the right structural parameter. The construction first extracts a small set of 'critical' shortest paths per terminal and records how they cross, then proves by linear-programming duality that edge weights realizing the terminal distances exist. The proof's hard part is showing that certain terminal flows cannot exist, which is done by morphing paths in the skeleton back to paths in the original graph while preserving flow dominance.

What carries the argument

The central machinery is the path-intersection viewpoint: the paper treats a graph as a family of terminal-to-terminal shortest paths together with the pattern of their crossings, rather than as a set of vertices and edges. From each terminal it keeps $O(f)$ 'critical' shortest paths, defined as the paths whose shape changes when the other endpoint scans over a terminal face; these are paired into primary and secondary paths, and the route between any two terminals is the canonical path formed by concatenating primary subpaths up to a bend. The skeleton is then drawn so that critical paths cross at most once, and edge weights are certified by a linear program ($LP$-$H^*$) whose feasibility is proved through linear-programming duality and flow dominance: infeasibility would create terminal flows $F$ dominating $F'$ with lower cost, and the proof shows these cannot exist by morphing canonical paths back to the original shortest paths through 'M-Areas', using Wye-$\Delta$ transformations to keep the capacity structure locally unchanged.

What would settle it

Recompute the minimum cut separating $u$ from $\{v,w\}$ in the Y-shaped graph with edge capacities $c(x,u)$, $c(x,v)$, and $c(x,w)$. If that cut value is the smaller of $c(x,u)$ and $c(x,v)+c(x,w)$ rather than $c(x,u)$, then the claimed equality between the Y and $\Delta$ cuts in the Wye-$\Delta$ step fails, and the flow-morphing proof must supply a different local argument before the theorem's weight-setting lemma is established.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1: for every edge-weighted planar graph $G$ with terminal set $T$ of size $k$ lying on $f$ faces of the embedding, there is an edge-weighted planar graph $H$ with $T \subseteq V(H)$ and $|V(H)| = O(f^2 k^2)$ such that $dist_H(t,t') = dist_G(t,t')$ for all $t,t' \in T$. The construction builds a central skeleton $H^*$ from critical paths and glues one-face emulators into its faces; distances between terminals on different faces are preserved by $H^*$, and distances on the same face by the one-face pieces. The theorem would place the known single-face bound $O(k^2)$ and the general bound $O(k^4)$ on a common curve indexed by the number of faces, with every intermediate value covered.

Load-bearing premise

The argument requires that locally rerouting a canonical path around a crossing never changes which terminal-flow demands are routable, so that a dominating flow in the skeleton can be carried back to the original graph; if any such rerouting changes routability, the linear-program feasibility proof for the edge weights collapses.

Editorial extensions

If this is right

  • If Theorem 1 is correct, the single-face bound $O(k^2)$ and the general bound $O(k^4)$ become the two endpoints of a single statement parameterized by the number of faces $f$, with $f=1$ and $f=k$ respectively.
  • For a constant number of faces $f$, every such planar instance has an exact planar emulator of size $O(k^2)$, matching the known lower bound up to constants.
  • The emulator preserves distances inside each face through the one-face constructions and across faces through the central skeleton, so the full terminal metric survives in the compressed graph.
  • The size bound follows from giving each terminal $O(f)$ critical paths and noting that any pair of critical paths crosses at most once, yielding $O(f^2 k^2)$ total vertices.
  • The LP-feasibility route gives a way to certify exact emulator weights without a closed formula, which the paper suggests may apply to other distance-based graph problems.

Reading between the lines

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

  • A direct consequence the paper leaves implicit is that the same $O(f^2 k^2)$ skeleton could serve distance queries between non-terminal vertices that also lie on those $f$ faces, since the skeleton is built from the same shortest-path structure.
  • If the local flow-equivalence step in the Wye-Delta argument is repaired, the statement of Theorem 1 would remain plausible, because the construction and the size bound do not depend on that local calculation.
  • The face-count parameter suggests a testable extension: worst-case planar instances may force emulators of size $\Omega(f^2 k^2)$, which would make the quadratic dependence on $f$ necessary rather than an artifact of the proof.
  • The existential LP-feasibility certificate could become a polynomial-time construction if a separation oracle for the dual flow conditions is found, potentially yielding an algorithmic version of the emulator construction.
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

3 major / 4 minor

Summary. The manuscript proposes exact planar distance emulators of size O(f^2 k^2) for k terminals lying on f faces, a result that would interpolate the known O(k^2) single-face bound and the known O(k^4) general bound. The construction first simplifies the input graph, extracts O(f) critical paths per terminal, forms a skeleton H* from their intersections, and defines canonical paths between terminals on different faces. Edge weights are then obtained by proving feasibility of a linear program; using Farkas' lemma, feasibility is reduced to a statement about terminal flows (Claim 19), and the main technical work (Claims 20 and 27) is to morph flows from H* into the original graph G. The paper concludes that H preserves terminal distances exactly.

Significance. If Theorem 1 were established, it would give a clean interpolation between the single-face and general planar emulator bounds, and it would further develop the paths-and-intersections viewpoint introduced in [CT25]. The skeleton construction and the LP-duality framework are original and clearly described, and the paper is explicit about borrowing the one-face emulator construction from [CO20] and [GHP20]. The main obstacle is correctness: the proof of the central flow-morphing claim rests on a false local statement, so the main result is not established by the submitted manuscript.

major comments (3)
  1. [§4.3, Observation 28] Observation 28 is false as stated. In a Y-shaped subgraph with a degree-three non-terminal x connected to terminals u,v,w with capacities c(x,u), c(x,v), c(x,w), the minimum cut separating u from {v,w} is min(c(x,u), c(x,v)+c(x,w)), not simply c(x,u), because the cut may place x on either side. For example, with capacities (3,1,1), the Y has a u-to-{v,w} cut of value 2, while the claimed Delta triangle has cut value c(u,v)+c(u,w)=3. In addition, the Wye-Delta capacity formulas can produce negative values, e.g., for capacities (1,1,3) the edge (v,w) would be assigned (1+1-3)/2 < 0. The formulas only define a valid capacitated graph if the path capacities a,b,c satisfy triangle inequalities, and no such inequalities are proved for the capacities appearing in Figure 28.
  2. [§4.3, Claim 27 and Figure 28] Claim 27 is the only mechanism that maintains routability of the F' demands during the flow-morphing process, and its proof relies entirely on the Wye-Delta equivalence asserted in Observation 28. Since Observation 28 is false, the local flow equivalence between the old and new graphs in Figure 28 is not established. Consequently Claim 20, which converts the dual flows in H* into flows in G, is unsupported, and Lemma 18, on which Theorem 1 depends, is not proven.
  3. [§4.3, Proof of Observation 28] Even apart from the incorrect min-cut computation, the reduction from global flow equivalence to local cut equivalence is not fully justified. The proof invokes Okamura-Seymour for the induced subgraphs on {u,v,w} and {u,v,w,x}, but the argument that a flow in the whole graph can be decomposed as a residual flow in the rest of the graph plus a flow through the local structure requires that the residual demand after removing the local edge flows be supported on {u,v,w}. The manuscript asserts this without a careful treatment of flows that enter or leave the local structure through x, and the notation f' is used for edges (u,v),(u,w),(v,w) even though these edges do not exist in the original Y graph. This part of the proof needs to be rewritten even if the cut computation were corrected.
minor comments (4)
  1. [§3.1, Step 1] There is a grammatical error in the sentence 'we remove from G all edges from that does not participate in any shortest path connecting a pair of terminals'; it should read 'edges from G that do not participate'.
  2. [§3.4.1, Areas] The definition of Area for pairs of critical paths is given informally with reference to figures; a formal definition in terms of the planar embedding would improve rigor, especially since the later proofs rely on containment and subset relations among these areas.
  3. [Appendix A.2, Proof of Observation 3] The proof refers to 'the counterclockwise segment between t'_{j1-1} and t'_{j3+1}' without specifying the indexing convention modulo the number of terminals on the face; this should be stated explicitly.
  4. [§4.3, Observation 28] The statement 'the minimum cut separating u from v and w' would be clearer as 'separating u from {v,w}', since v and w are treated as a single group in the relevant partition.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: central construction and LP-feasibility proof are self-contained; shared-author citations are motivational only.

full rationale

The derivation chain is self-contained rather than circular. The construction uses [CT25] only as methodological inspiration ('viewing graphs as paths and their intersections' and the LP-duality framework), and the paper supplies its own proofs for the O(f) critical-path bound (Lemma 4), the iterative skeleton construction (Section 3.4), the LP feasibility reduction (Claim 19 via Farkas), and the flow-morphing argument (Claim 20). The one-face emulators of [CO20, GHP20] are used as external building blocks, not as the f-face result itself, and the claimed interpolation with [KNZ14] does not import that paper's proof. The f=k endpoint is not obtained by renaming [KNZ14]; it is the same asymptotic bound but reached through the new skeleton. The only shared-author citations ([CT25], [CKT22]) are non-load-bearing: they motivate the approach or appear in related-work statements, and no uniqueness theorem or fitted quantity is imported. The Wye-Delta cut computation flagged by a reader (Observation 28) is a possible correctness defect, not a circularity: if wrong, the proof is unsupported, but it does not make the theorem reduce to its inputs. Therefore no circular step can be exhibited.

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

No fitted parameters appear in this theory paper. The proof relies on the simplifying redrawing assumptions, on the Okamura-Seymour theorem, and on the Wye-Delta transformation, with the Wye-Delta step being the most fragile and unsupported.

assumptions (5)
  • standard math Unique shortest paths can be assumed via lexicographic perturbation without changing terminal distances or face structure.
    Section 3.1, preparation for Property G3; invokes the lexicographic perturbation scheme of [EFL18]. Standard technique, but it modifies edge weights and the paper does not prove that all terminal distances and face incidences are preserved.
  • domain assumption The redrawing process in Section 3.1 (channels, discs, strips, uncrossing of curves) yields a graph that preserves terminal distances, face incidence, and the crossing structure of shortest paths.
    Section 3.1, steps 1-7; the paper states 'It is easy to verify' without a full proof. This is load-bearing for Property G3 and for the subsequent skeleton construction.
  • domain assumption Two critical paths from the same terminal intersect only at the terminal itself.
    Used in the proof of Lemma 4 (O(f) critical paths per terminal). Depends on the redrawing producing at most one crossing per pair of curves and on the separation of shared subpaths, which is not formally established in the text.
  • standard math Okamura-Seymour: in planar graphs with all terminals on the outer boundary, the cut condition is sufficient for multiflows.
    Used in Observation 28 to reduce the flow equivalence of the Y and Delta structures to terminal-cut equivalence. This is a standard theorem [OS81].
  • ad hoc to paper The Wye-Delta and Delta-Wye operations with the stated capacity formulas preserve terminal flow equivalence for the local structures in Figure 28.
    Claim 27 relies on this. The proof in Observation 28 computes min-cut values incorrectly and does not address nonnegativity of the transformed capacities, so the assumption may be false in general.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Paths and Intersections: Exact Emulators for Planar Graphs." pith.science (2026). https://pith.science/paper/PHUN6HXI

@misc{pith2026250709620,
  author       = {Pith},
  title        = {Pith review of: Paths and Intersections: Exact Emulators for Planar Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PHUN6HXI}},
  note         = {Machine review of arXiv:2507.09620}
}
abstract

We study vertex sparsification for preserving distances in planar graphs. Given an edge-weighted planar graph with $k$ terminals, the goal is to construct an emulator, which is a smaller edge-weighted planar graph that contains the terminals and exactly preserves the pairwise distances between them. We construct exact planar emulators of size $O(f^2k^2)$ in the setting where terminals lie on $f$ faces in the planar embedding of the input graph. Our result generalizes and interpolates between the previous results of Chang and Ophelders and Goranci, Henzinger, and Peng which is an $O(k^2)$ bound in the setting where all terminals lie on a single face (i.e., $f=1$), and the result of Krauthgamer, Nguyen, and Zondiner, which is an $O(k^4)$ bound for the general case (i.e., $f=k$). Our construction follows a recent new way of analyzing graph structures, by viewing graphs as paths and their intersections, which we believe is of independent interest.

Figures

Figures reproduced from arXiv: 2507.09620 by the authors.

Figure 1
Figure 1. An illustration of the quarter-grid construction in [CO20]. Terminals (purple) lie on the [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. An illustration of t4 splitting at (t ′ 4 , t′ 5 ). Paths P4,4 and P4,5 are critical paths from t4. Furthermore, we can show that, as we move from terminal to terminal clockwise on the outer face, their “split location” also moves clockwise on the inner face. The proof is deferred to Appendix A.2. Observation 3. Let ti1 , ti2 , ti3 be terminals on the outer face clockwise in this order. If ti1 , ti2 , ti3 split at (… view at source ↗
Figure 3
Figure 3. An illustration of the structure of H. Left: the picture after adding all curves. The curves corresponding to the critical paths of t4 are shown in pink. Right: the grid-shape structure after reorganizing the location of terminals. Each intersection between a horizontal line and a vertical line represents a new vertex. The down edge from t7 connects to the second vertex on the first row (both marked a), and similarl… view at source ↗
Figures from the paper (26 more)
Figure 4
Figure 4. Figure 4: If the t1-t ′ 3 shortest path follows the “down-right” route (shown in green), while the t1-t ′ 4 shortest path follows the “right-down” route (shown in black), then this will create a pair of vertices with multiple shortest paths between them, which is undesired. To s…
Figure 5
Figure 5. Figure 5: An illustration of O(f) critical paths from a terminal in a f-face instance. 3 The f-face Case: Constructing the Graph In this section we provide the proof of Theorem 1. Recall that we are given a plane graph G and a set T of its vertices called terminals, such that al…
Figure 6
Figure 6. Figure 6: An illustration of replacing shortest paths with curves. The red vertex in the original [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: All critical paths (green) from terminal [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]
Figure 8
Figure 8. Figure 8: An illustration of multiple crossings between the [PITH_FULL_IMAGE:figures/full_fig_p016_8.png]
Figure 9
Figure 9. Figure 9: An illustration of Area((x, y),(x ′ , y′ )) (pink). 3We will mostly use the notions areas to describe a type of “morphing” process that we will use later. Essentially, morphing corresponds to continuous deformation between a pair of homotopic simple curves (when termin…
Figure 10
Figure 10. Figure 10: An illustration of the shape of the u-v canonical path (red). Observation 7. Fix two faces F1 and F2, where F1 has a lower face index than F2. Let (u, v′ ) be a primary path from u to F2 and (v, u′ ) be a primary path from v to F1, that form the u-v canonical path wit…
Figure 11
Figure 11. Figure 11: Notations for relevant nodes induced by a bad pair. [PITH_FULL_IMAGE:figures/full_fig_p019_11.png]
Figure 12
Figure 12. Figure 12: In the figures, the pink shaded region is [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]
Figure 13
Figure 13. Figure 13: An illustration of examples of Area((a, b),(at , bt)) in orange, Area((at , bt),(at+1, bt+1)) in pink, and Area((a, b),(at+1, bt+1)) outlined in red. In each of the three examples, we can see that Area((a, b),(at+1, bt+1)) is a subset of Area((a, b),(at , bt)) ∪ Area(…
Figure 14
Figure 14. Figure 14: In the left figure, we assert that the critical path ( [PITH_FULL_IMAGE:figures/full_fig_p022_14.png]
Figure 15
Figure 15. Figure 15: In each of the figures, (h, d, i) represents ∆T −1, the pink area represents ∆T , and the red curve represents the path S. In the top two figures, any path S which crosses ∆T twice must also cross ∆T −1 twice. In the bottom figure, a path S which crosses ∆T twice but …
Figure 16
Figure 16. Figure 16: The right figure illustrates what actually happens: the triangle ( [PITH_FULL_IMAGE:figures/full_fig_p024_16.png]
Figure 17
Figure 17. Figure 17: The left figure illustrates the sequence of areas [PITH_FULL_IMAGE:figures/full_fig_p024_17.png]
Figure 18
Figure 18. Figure 18: Illustrates the rerouting of (a, b) over the triangle (h, i, d). an area which is a subset of Area(h, i, d) which doesn’t contain any terminal faces or terminals (Observation 8). Consequently, the difference between A and A′ doesn’t enclose any terminal or face. Since…
Figure 19
Figure 19. Figure 19: An illustration of the proof of Observation 14. The two crossings which must occur [PITH_FULL_IMAGE:figures/full_fig_p026_19.png]
Figure 20
Figure 20. Figure 20: In all subfigures, (u, v) and (v, w) are represent by blue lines. The former three cases are not possible by a similar argument as in the caption of 15 via Observation 7. The final case is not possible by minimality of the triangle. Observation 14, we may assume witho…
Figure 21
Figure 21. Figure 21: In both figures, the blue path represents [PITH_FULL_IMAGE:figures/full_fig_p027_21.png]
Figure 22
Figure 22. Figure 22: Each canonical path covers a prefix of the critical path [PITH_FULL_IMAGE:figures/full_fig_p032_22.png]
Figure 23
Figure 23. Figure 23: An illustration of splitting a canonical path: Before (left) and after (right). [PITH_FULL_IMAGE:figures/full_fig_p033_23.png]
Figure 24
Figure 24. Figure 24: An illustration of the construction of H and the new F ′ -routing on it. When all iterations are finished, remove from H all the original critical paths; that is H ← H \ H∗ . Finally, we need to show that we can reroute F ′ , still satisfying Property P2. Claim 22. Th…
Figure 25
Figure 25. Figure 25: In the left figure, (a, b, c) is the current triangle with crossing at a. The red signs along (a, c) indicate that the new γc can never cross (a, c). Hence, the new γc (drawn in orange) must cross (a, b) and (b, c), decreasing the size of the triangle (a, b, c). The r…
Figure 26
Figure 26. Figure 26: In both cases, the red path illustrates the morphing of [PITH_FULL_IMAGE:figures/full_fig_p036_26.png]
Figure 27
Figure 27. Figure 27: An illustration of the Delta-Wye transformation (applying on the left graph to obtain [PITH_FULL_IMAGE:figures/full_fig_p038_27.png]
Figure 28
Figure 28. Figure 28: In the above sequence, we show that locally the old graph [PITH_FULL_IMAGE:figures/full_fig_p039_28.png]
Figure 29
Figure 29. Figure 29: An illustration of graphs H1, H2, H3 and graph H (right) obtain by concatenating them. B Proof of Claim 19 We use the following Farkas’ lemma [Far98]. Lemma 29 (Farkas’ Lemma). For any matrix A ∈ R m×n and any vector b ∈ R m, exactly one of the two assertions holds: •…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Paths and Intersections: Minimum Realization of Okamura-Seymour Instances

    cs.DS 2026-07 accept novelty 7.0 of 10

    Every OS metric has a unique minimum-crossing medial template; its primal arrangements are precisely the fewest-edge disk realizations, recoverable with realizing lengths in polynomial time.

  2. Paths and Intersections: Recognizing Outerplanar Metrics

    cs.DS 2026-06 unverdicted novelty 7.0 of 10

    Outerplanar metrics admit an O(k^5) recognition algorithm but no O(1)-point local characterization, proved via a repelling-paths condition on shortest-path structures.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · cited by 2 Pith papers

  1. [1]

    Steiner point removal in graph metrics

    Amitabh Basu and Anupam Gupta. Steiner point removal in graph metrics. Unpublished Manuscript, available from http://www. math. ucdavis. edu/\ abasu/papers/SPR. pdf , 1:25, 2008

    work page 2008

  2. [2]

    Covering planar metrics (and beyond): O(1) trees suffice

    Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. Covering planar metrics (and beyond): O(1) trees suffice. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2231--2261. IEEE, 2023

    work page 2023

  3. [3]

    Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more

    Hsien - Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. Shortcut partitions in minor-free graphs: Steiner point removal, distance oracles, tree covers, and more. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024 , pages 5300--5331. SIAM , 2024

    work page 2024

  4. [4]

    Near-optimal distance emulator for planar graphs

    Hsien - Chih Chang, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. Near-optimal distance emulator for planar graphs. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms, ESA 2018 , volume 112 of LIPIcs , pages 16:1--16:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2018

    work page 2018

  5. [5]

    Steiner point removal: distant terminals don't (really) bother

    Yun Kuen Cheung. Steiner point removal: distant terminals don't (really) bother. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1353--1360. Society for Industrial and Applied Mathematics, 2018

    work page 2018

  6. [6]

    Almost-linear -emulators for planar graphs

    Hsien-Chih Chang, Robert Krauthgamer, and Zihan Tan. Almost-linear -emulators for planar graphs. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1311--1324, 2022

    work page 2022

  7. [7]

    Planar emulators for Monge matrices

    Hsien - Chih Chang and Tim Ophelders. Planar emulators for Monge matrices. In J. Mark Keil and Debajyoti Mondal, editors, Proceedings of the 32nd Canadian Conference on Computational Geometry, CCCG 2020 , pages 141--147, 2020

    work page 2020

  8. [8]

    An O( |T|) lower bound for Steiner point removal

    Yu Chen and Zihan Tan. An O( |T|) lower bound for Steiner point removal. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 694--698. SIAM, 2024

    work page 2024

Show all 20 references
  1. [9]

    Path and intersections: Characterization of quasi-metrics in directed Okamura-Seymour instances

    Yu Chen and Zihan Tan. Path and intersections: Characterization of quasi-metrics in directed Okamura-Seymour instances. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2467--2490. SIAM, 2025

    2025

  2. [10]

    A tight lower bound for the Steiner point removal problem on trees

    T-H Hubert Chan, Donglin Xia, Goran Konjevod, and Andrea Richa. A tight lower bound for the Steiner point removal problem on trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , pages 70--81. Springer, 2006

    2006

  3. [11]

    Holiest minimum-cost paths and flows in surface graphs

    Jeff Erickson, Kyle Fox, and Luvsandondov Lkhamsuren. Holiest minimum-cost paths and flows in surface graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 1319--1332, 2018

    2018

  4. [12]

    A Fourier -f \'e le mechanikai elv algebrai alapja

    Gyula Farkas. A Fourier -f \'e le mechanikai elv algebrai alapja. Math \'e matikai \'e s Term \'e szettudom \'a nyi Ertesito , 16:361--364, 1898

  5. [13]

    Steiner point removal with distortion O( k) using the relaxed- Voronoi algorithm

    Arnold Filtser. Steiner point removal with distortion O( k) using the relaxed- Voronoi algorithm. SIAM J. Comput. , 48(2):249--278, 2019

    2019

  6. [14]

    Scattering and sparse partitions, and their applications

    Arnold Filtser. Scattering and sparse partitions, and their applications. ACM Trans. Algorithms , 20(4):30:1--30:42, 2024

    2024

  7. [15]

    Improved guarantees for vertex sparsification in planar graphs

    Gramoz Goranci, Monika Henzinger, and Pan Peng. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics , 34(1):130--162, 2020

    2020

  8. [16]

    Steiner points in tree metrics don't (really) help

    Anupam Gupta. Steiner points in tree metrics don't (really) help. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms , pages 220--227. Society for Industrial and Applied Mathematics, 2001

    2001

  9. [17]

    Ellis Hershkowitz and Jason Li

    D. Ellis Hershkowitz and Jason Li. O(1) Steiner point removal in series-parallel graphs. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022 , volume 244 of LIPIcs , pages 66:1--66:17. Schloss D...

    2022

  10. [18]

    Cutting corners cheaply, or how to remove Steiner points

    Lior Kamma, Robert Krauthgamer, and Huy L Nguyen. Cutting corners cheaply, or how to remove Steiner points. SIAM Journal on Computing , 44(4):975--995, 2015

    2015

  11. [19]

    Preserving terminal distances using minors

    Robert Krauthgamer, Huy L Nguyen, and Tamar Zondiner. Preserving terminal distances using minors. SIAM Journal on Discrete Mathematics , 28(1):127--141, 2014

    2014

  12. [20]

    Multicommodity flows in planar graphs

    Haruko Okamura and Paul D Seymour. Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B , 31(1):75--81, 1981

    1981

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.