Pith. sign in

REVIEW 3 major objections 3 minor 59 references

Minimum Monotone Spanning Trees

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

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

Pith's one-line read For any fixed set of directions, the shortest spanning tree whose every path is monotone can be computed in polynomial time; for two directions, in quadratic time.

desk verdict New problem, a real structural characterization, and XP algorithms with a fixable gap at k>=3; worth a serious referee. read the letter →

arxiv 2411.14038 v3 pith:UF5ZPED3 submitted 2024-11-21 cs.CG

Emilio Di Giacomo , Walter Didimo , Eleni Katsanou , Lena Schlipf , Antonios Symvonis , Alexander Wolff This is my paper · ORCID
classification cs.CG MSC 68U0505C0568W40
keywords monotonespanningtreeD-monotoneminimumdrawingcomputationalgeometryXPalgorithmhomeomorphicallyirreduciblevertexdegreebound
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

Minimum spanning trees are classically easy to compute, but this paper adds a geometric constraint: every path between two vertices must be monotone, meaning the vertices appear in the same order as their projections on a line, with the direction of monotonicity chosen from a prescribed set $D$. The paper proves a structural characterization of such $D$-monotone spanning trees and uses it to show that a shortest one can be found in polynomial time for any fixed number of directions, and in quadratic time for two directions. When the direction set is not prescribed, choosing the best $k$ directions is also polynomial for every fixed $k$, with explicit $O(n^2 \log n)$ and $O(n^6)$ algorithms for $k=1$ and $k=2$. The paper also shows that monotonicity can force large degree: for every even $k$ there is a point set whose unique shortest $k$-monotone spanning tree is a star of degree $2k$, in contrast to the classical Euclidean minimum spanning tree, whose degree is at most six.

What carries the argument

The machinery is the decomposition of a $D$-monotone spanning tree into leaf paths and branches, each carrying a wedge set. With $k$ directions, the lines through a point perpendicular to those directions cut the plane into $2k$ wedges; the wedge set of a directed path is the smallest consecutive block of wedges containing all directions that path travels in. Two derived objects do the work: $W_{u\setminus v}(u)$, the wedge region of the subtree at $u$ that avoids $v$, and $R_{u,v}$, the region of the branch or leaf path between $u$ and $v$. Theorem 1 makes monotonicity equivalent to three conditions on these objects, Lemma 11 shows that a fixed tree shape, vertex mapping, and wedge assignment determine a unique candidate tree in $O(n \log n + nk + k)$ time, and a counting lemma bounds the number of homeomorphically irreducible trees (embedded trees with no degree-2 vertices) with at most $\ell$ leaves by $O(7^\ell \ell!)$.

What would settle it

Run an exhaustive search over all small point sets in general position with, say, six points and $k=2$ or $k=3$: check whether the spanning trees satisfying conditions (a)–(c) of Theorem 1 are exactly the $D$-monotone spanning trees, and whether the best tree over all $k$-direction sets is matched by the best tree using only directions from slopes of point pairs. A single mismatch in either test would refute the characterization or the direction-restriction claim on which the XP algorithms rest.

Watch

Extended reading notes

Core claim

The central claim is a characterization (Theorem 1): a spanning tree $T$ of a point set $S$ is $D$-monotone if and only if (a) every leaf path and every branch of $T$ is $D$-monotone, (b) the wedge sets of any two leaf paths are disjoint, and (c) for every branch or leaf path $P_{u,v}$, the region $R_{u,v}$ of that path is disjoint from the wedge region $W_{u\setminus v}(u)$ of the subtree hanging from $u$ away from $v$. This turns a condition on every pair of vertices into local conditions on $O(k)$ paths, which is what makes enumeration feasible. The paper argues that once a tree shape, a mapping of branching vertices to points, and an assignment of the $2k$ wedges to leaves are fixed, the optimal tree is unique and can be built in near-linear time by sorting points along two boundary directions. Enumerating shapes, mappings, and wedge assignments yields the XP algorithm for a prescribed direction set, and applying that over direction sets drawn from the slopes of point pairs yields the XP algorithm for choosing $k$ directions.

Load-bearing premise

The load-bearing premise is that, for $k \ge 3$, no optimal direction set is lost by restricting to directions taken from the finite list of slopes of lines through pairs of input points and by perturbing the points into general position; the paper states that an exchange argument proves this, but does not supply the argument.

Editorial extensions

If this is right

  • For every fixed $k$, both versions of the problem — directions prescribed or directions chosen — can be solved in polynomial time, with exponents linear in $k$ for the prescribed case and quadratic in $k$ for the chosen case.
  • A $D$-monotone spanning tree has at most $2k$ leaves and maximum degree at most $2k$, so the enumeration over tree shapes is finite and the degree bound is tight in the worst case.
  • For two prescribed directions, the minimum $D$-monotone spanning tree can be found in $O(n^2)$ time, improving the generic $O(n^3 \log n)$ bound for that case.
  • For choosing one direction, the optimum is a monotone spanning path, computable in $O(n^2 \log n)$ time by sweeping the circular sequence of directions defined by slopes of point pairs.
  • The shortest $k$-monotone spanning tree can be forced to have a vertex of degree $2k$, so monotonicity, unlike the Euclidean MST property, does not keep degrees small.

Reading between the lines

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

  • The characterization suggests a recognition algorithm the paper does not spell out: a given geometric spanning tree can be checked for $D$-monotonicity by testing the $O(k)$ conditions (a)–(c) rather than all vertex pairs.
  • The degree-$2k$ lower bound hints that monotone trees behave like hub-and-spoke structures under restricted direction sets, which could matter for routing or network design where paths must be non-backtracking; the paper does not explore applications.
  • A natural stress test for the XP algorithm is to compare the length of the shortest $k$-monotone spanning tree with the ordinary Euclidean MST on random point sets; the paper gives no computational data, and the gap should grow with $k$ and with anisotropy of the point distribution.
  • The XP results leave open whether the direction-choice problem stays polynomial when $k$ is part of the input; the next target is to prove NP-hardness for variable $k$ or to find a fixed-parameter-tractable algorithm.
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 / 3 minor

Summary. The paper introduces the minimum monotone spanning tree problem. For a point set S and a set D of directions, a spanning tree is D-monotone if the unique path between every pair of vertices is monotone with respect to some direction in D. The central contribution is a structural characterization (Theorem 1) of D-monotone spanning trees in terms of wedge sets of leaf paths, branches, and disjointness conditions. Using this characterization, the authors give an XP algorithm for MMST(S,D) parameterized by |D|, an O(n^2)-time algorithm for |D|=2, algorithms for MMST(S,k) for k=1 and k=2, an XP algorithm for general k, and a construction showing that minimum k-directional monotone spanning trees can have degree 2k, in contrast to the degree bound 6 for Euclidean MSTs. The proofs are largely self-contained, with several details deferred to appendices.

Significance. If the results are correct, the paper contributes a reusable structural characterization of D-monotone spanning trees and establishes exact complexity-theoretic upper bounds (XP) for natural parameterized geometric optimization problems. The algorithms are deterministic and are derived from the characterization rather than from heuristic fitting or numerical search, which is a strength. The degree-2k construction is a clean and explicit counterpoint to the bounded-degree property of classical Euclidean MSTs. The main caveat is that the XP claim for MMST(S,k) with k >= 3 depends on an unproven exchange argument in the proof of Theorem 7; this part of the paper needs to be completed or corrected before the advertised result can be considered established.

major comments (3)
  1. [Appendix C, proof of Theorem 7] The step limiting the search to k-tuples of directions from the Goodman-Pollack sequence sigma is not proved for k >= 3. The proof says only: "By using an exchange argument as in the proof of Theorem 6, it can be proven that it is sufficient to restrict ourselves to sets D of k directions for which S is in D-general position." Theorem 6 covers only k = 2 and perturbs one direction while keeping the other fixed. For k >= 3 one must show that an optimal D-monotone tree T remains D'-monotone under a simultaneous perturbation D' of all k directions, and that each perturbed direction can be replaced by a direction from sigma without increasing the optimum. This is load-bearing because the abstract claims that MMST(S,k) is in XP for every k. The gap appears repairable, e.g., by intersecting the open monotonicity intervals of all paths in T and selecting generic directions with representatives in sigma, but the argument must be supplied in full.
  2. [Appendix C, Theorem 7] The stated running time is arithmetically inconsistent with the proof. The proof applies Theorem 2, which has running time O(f(k) * n^{2k-1} log n), to each of the C(h,k) = O(n^{2k}) direction sets obtained from sigma, yielding O(f(k) * n^{4k-1} log n) after absorbing h = O(n^2). The paper instead claims O(f(k) * n^{2k(2k-1)} log n). The corrected bound is still in XP, but the stated complexity should be fixed.
  3. [Theorem 1, proof of converse direction] The induction step in the proof of the converse direction of Theorem 1 asserts that if both the leading and trailing wedges of W_{P_m} change when passing to W_{P_{m+1}}, then |W_{B_{b_{m+1},b_m}}| > k. This is plausible but is stated without a formal argument, and it is essential for the characterization on which all subsequent algorithms rest. Please expand this step so that the reader can verify the wedge counting in the case analysis, especially with respect to the orientation of the branch B_{b_m,b_{m+1}}.
minor comments (3)
  1. [Theorem 1, proof of converse direction] In the last paragraph of the proof, the expression "W_{P_m}(b_m) \subset W_{b_m,b_{m+1}}(b_m)" appears to contain a typographical error: W_{b_m,b_{m+1}} is not defined, and the intended set is presumably W_{b_m \setminus b_{m+1}}. Please correct the subscript.
  2. [Appendix C, Theorem 7] The final sentence of the proof says "it is sufficient to restrict ourselves to sets D of k directions for which S is D-monotone." This should read "S is in D-general position," since the former is a property of trees, not of point-direction pairs.
  3. [Appendix B, proof of Lemma 11] There is a typo in the sentence "The assignment A of the wedges of WD to the leaves of H defines, for each leaf path, a reagion that must contain it." Replace "reagion" with "region."

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the new characterization drives the algorithms, and the only flagged issues are an unproven exchange argument and a runtime exponent slip, neither of which assumes the conclusion.

full rationale

The derivation chain is self-contained. Theorem 1 characterizes D-monotone spanning trees via conditions (a)-(c); its necessity direction uses Lemma 6(ii) and Lemma 9, and its sufficiency direction builds a leaf-to-leaf path from leaf paths and branches and uses Corollary 1 (from Lemma 5) together with an induction on the branch sequence, never assuming that the target path is D-monotone. Lemma 5 and Corollary 1 are proved directly from the projection definition of monotonicity. The algorithms of Lemma 11 and Theorem 2 are enumerations over HITs, point mappings, and wedge assignments; their correctness is reduced to Theorem 1, and Lemma 11's solution uniqueness follows from sorted unique monotone paths inside each region, not from a fitted parameter. For MMST(S,k), Theorem 5 enumerates the Goodman-Pollack direction sequence and proves every 1-directional monotone path is represented because its monotonicity interval is an open sector bounded by lines in L; Theorem 6 gives the rotation argument for two directions. The only flagged issues are in Appendix C (Theorem 7): the statement 'By using an exchange argument as in the proof of Theorem 6, it can be proven that it is sufficient to restrict ourselves to sets D of k directions for which S is in D-general position' is an omitted proof for k>=3, and the stated runtime O(f(k)n^{2k(2k-1)}log n) does not follow from C(h,k) in O(n^{2k}) applications of an O(f(k)n^{2k-1}log n) procedure, which gives O(f(k)n^{4k-1}log n). These are correctness risks, not circularity, because neither assumes the optimality of the enumerated set. Self-citations to Mastakas and Symvonis are related work; the load-bearing monotone-path lemma (Lemma 4) is external and standard, and no claim reduces to a self-citation. Hence no circular step occurs.

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

No free parameters are fitted to data. The paper introduces no new physical or ontological entities; wedge sets and HITs are mathematical objects used in proofs. The axioms are the standard background of Euclidean computational geometry and two cited prior results.

assumptions (4)
  • standard math A path is monotone iff its sector of directions has angle less than pi (Lemma 4 of Angelini et al.).
    Borrowed from prior literature; used in Corollary 1 and throughout Section 4.
  • domain assumption Real RAM model with exact real arithmetic.
    All runtime bounds assume exact real computations; standard for computational geometry.
  • domain assumption Point set S is in d-general position for the directions used, or degeneracies are handled by perturbation.
    Definitions of orderings and wedge sets need general position; degenerate cases are handled for k=1,2 and asserted for k>=3 via an exchange argument.
  • standard math The Goodman-Pollack circular sequence of O(n^2) slopes captures all relevant monotone spanning paths.
    Used in Theorems 5, 6, and 7 to discretize the space of directions; cited from [26].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimum Monotone Spanning Trees." pith.science (2026). https://pith.science/paper/UF5ZPED3

@misc{pith2026241114038,
  author       = {Pith},
  title        = {Pith review of: Minimum Monotone Spanning Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UF5ZPED3}},
  note         = {Machine review of arXiv:2411.14038}
}
abstract

Given a finite set $S$ of points in the plane and a finite set $\mathcal{D}$ of directions, a geometric spanning tree~$T$ of~$S$ is $\mathcal{D}$-monotone if every path in $T$ is monotone with respect to some direction in $\mathcal{D}$. We study the problem of computing, for a given point set $S$ and a given set $\mathcal{D}$ of directions, a minimum-length $\mathcal{D}$-monotone spanning tree of~$S$. We present a quadratic-time algorithm for two directions. More generally, we show that the problem belongs to the complexity class XP when parameterized by the number of directions. We further study, for a given positive integer $k$ and point set~$S$, the problem of finding a minimum-length $\mathcal{D}$-monotone spanning tree of $S$ over all possible sets~$\mathcal{D}$ of $k$ directions. We prove that this problem, too, is in XP when parameterized by~$k$, and present two algorithms that run in $O(n^2 \log n)$ and $O(n^6)$ time for $k=1$ and $k=2$, respectively, where $n$ is the number of points in~$S$. Finally, in contrast to the classical Euclidean minimum spanning tree of a set of points, whose vertex degree is bounded by six, we show that for every even integer~$k$, there exists a point set~$S_k$ and a set $\mathcal{D}_k$ of $k$ directions such that any minimum-length $\mathcal{D}_k$-monotone spanning tree of $S_k$ has maximum vertex degree~$2k$.

Figures

Figures reproduced from arXiv: 2411.14038 by the authors.

Figure 1
Figure 1. (a) A point set S with its Delaunay triangulation, (b) MST of S, (c) MMST of S w.r.t. { [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 3
Figure 3. (a) A directed geometric path P, (b) its sector of directions sec(P) (in dark gray) and (c) the wedge set WP of path P (in blue). A minimum D-monotone spanning tree of S is a D-monotone spanning tree of S of minimum length among all D-monotone spanning trees of S; we call MMST(S, D) the problem of computing such a tree. For a positive integer k, we say that a spanning tree T of S is k-directional monotone if there e… view at source ↗
Figure 4
Figure 4. (a) A monotone tree and its sets of utilized wedges for each leaf path. (b) All sets of utilized wedges drawn on the same unit circle. Set Wu\v (resp. Wv\u) consists of all wedges in the blue (resp. gray) region. that p is its apex. If ←− P is the reverse path of P, then W←− P consists of the wedges opposite to those in WP . We say that path P utilizes wedge set WP . In a D-monotone spanning tree T, a branching vert… view at source ↗
Figures from the paper (17 more)
Figure 5
Figure 5. Figure 5: The different shapes of Ru,v depending on |WBu,v |. Let Bu,v be a branch of a D-monotone tree T connecting branching vertices u and v. Recall that |WBu,v | ≤ k, due to monotonicity of Bu,v. Let Ru,v = WBu,v (u) ∩ WBv,u (v). If |WBu,v | < k, then Ru,v is a parallelogram…
Figure 6
Figure 6. Figure 6: Different cases examined in the proof of Theorem 1 in D such that d(u) separates WPu,λ (u) and WPv,µ (v) and does not intersect the interior of either of them. By Corollary 1, Pu,λ and Pv,µ are both d-monotone and, additionally, they lie in different halfplanes with re…
Figure 7
Figure 7. Figure 7: A leaf path P that is assigned seven wedges but utilizes only five of them (shaded darkgray): It is not monotone with respect to {d3, d4, d5, d6}. of type MMST(S, D, H, M, A) is repeatedly used by the algorithm that proves Theorem 2. Lemma 11 (⋆). Let S be a set of n p…
Figure 8
Figure 8. Figure 8: (a) The point set Sk is defined based on the set WD of wedges (red dashed). (b) The path setting exploited in the proof of Theorem 3. (c) A monotone spanning graph of the point set in Fig. 8a whose length is much smaller than the 2k-star in (a). that the unique solutio…
Figure 9
Figure 9. Figure 9: The path ⟨u, x, v⟩ is not d-monotone [PITH_FULL_IMAGE:figures/full_fig_p017_9.png]
Figure 10
Figure 10. Figure 10: (a) Line d(o) intersects sec(P). (b) Line d(pi) does not intersect sec(P). Lemma 5 (⋆). Given a direction d, a monotone directed geometric path P is d-monotone if and only if d(o) does not intersect sec(P), where o is the origin. Proof. Assume first that P = ⟨p1, . . …
Figure 11
Figure 11. Figure 11: Monotone embedded tree used in the proof of property Lemma 8(ii). Thus, path P ′ is, at least, utilizing all wedges also utilized by either P1 or P2. Without loss of generality, assume that WP ′ intersects with WP1 . However, given that both P ′ and P1 are edge-disjoi…
Figure 12
Figure 12. Figure 12: A HIT with three leaves and all nine HITs that can be generated from it by means of Operations 1 and 2. If we perform Operation 2 on an edge e of T, we can obtain 2 different HITs depending on the side of e where the new edge is added. Thus, from the tree T we can obt…
Figure 13
Figure 13. Figure 13: Gray regions are the wedges not utilized by any leaf path. The red arrows indicate the leaf the wedge is assigned to as described in the proof of Theorem 2. It remains to show the correctness of our approach. Towards that goal it is sufficient to show that for any D-m…
Figure 14
Figure 14. Figure 14: Different topologies of a spanning tree that is monotone w.r.t. D = {d1, d2}. at most four leaves. Hence, by Lemma 10, there are only O(1) different HITs, namely the D-path and the topologies depicted in [PITH_FULL_IMAGE:figures/full_fig_p025_14.png]
Figure 15
Figure 15. Figure 15: 1. If qy < m′ y , then q fails the test because the points m and m′ both dominate it directly; see Fig. 15a. Set the flag of q to false [PITH_FULL_IMAGE:figures/full_fig_p026_15.png]
Figure 15
Figure 15. Figure 15: The three cases that occur in the iterative algorithm. 2. If m′ y < qy < my, then set the flag of q to true, establish a pointer from q to m, and set m = q; see Fig. 15b. 3. If my < qy, then we follow pointers from m to its successors as long as the current point is b…
Figure 16
Figure 16. Figure 16: Point set S = {1, 2, 3, 4} and illustration of the computation of a set of distinct directions over which the minimum monotone spanning path of S is computed. in our construction the two points that define it. Hence, the algorithm computes all paths defined by σ and t…
Figure 17
Figure 17. Figure 17: Point set S = {1, 2, . . . , 9} consists of three sets of collinear points that form pairs having the line passing through them perpendicular to l1,2(o) and its orderings ord(S, di) and ord(S, di+1) on di(o) and di+1(o), respectively. Note that the connected component…
Figure 18
Figure 18. Figure 18: (a) All but one wedges in WD(x) contains two polygon vertices. (b-d) The path setting exploited in the proof of Lemma 15. P should lie between lines di(u1) and di(w2). This is again, a contradiction, because the strip bounded by these two lines does not contain vertex…
Figure 19
Figure 19. Figure 19: Connections of degree-two vertices in the proof of Lemma 12 two consecutive polygon vertices lying in different wedges of WD(x) and separated by di(x), for some direction di ∈ D, 1 ≤ i ≤ k. Then, path P = ⟨w1, . . . , o, x, u2, . . . , w2⟩ must be di-monotone, which o…
Figure 20
Figure 20. Figure 20: The path setting exploited in the proof of Theorem 3. Consider now a polygon vertex u of degree one that is connected to T with an external polygon edge. For easiness of presentation, we rotate the point set (and we renumber the vertices accordingly) so that u coincid…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 44 canonical work pages

  1. [1]

    Chan, Elyot Grant, Anna Lubiw, and Vinayak Pathak

    Soroush Alamdari, Timothy M. Chan, Elyot Grant, Anna Lubiw, and Vinayak Pathak. Self-approaching graphs. In Walter Didimo and Maurizio Patrignani, editors, Proc. 20th Int. Symp. Graph Drawing (GD’12), volume 7704 of LNCS, pages 260–271. Springer, 2012. doi:10.1007/978-3-642-36763-2\_23

    doi:10.1007/978-3-642-36763-2 2012

  2. [2]

    Monotone drawings of graphs with few directions

    Patrizio Angelini. Monotone drawings of graphs with few directions. Inform. Process. Lett., 120:16–22, 2017. doi:10.1016/j.ipl.2016.12.004

    work page doi:10.1016/j.ipl.2016.12.004 2017

  3. [3]

    Bekos, Walter Didimo, Luca Grilli, Philipp Kinder- mann, Tamara Mchedlidze, Roman Prutkin, Antonios Symvonis, and Alessandra Tappini

    Patrizio Angelini, Michael A. Bekos, Walter Didimo, Luca Grilli, Philipp Kinder- mann, Tamara Mchedlidze, Roman Prutkin, Antonios Symvonis, and Alessandra Tappini. Greedy rectilinear drawings. Theor. Comput. Sci., 795:375–397, 2019. doi:10.1016/J.TCS.2019.07.019

    work page doi:10.1016/j.tcs.2019.07.019 2019

  4. [4]

    Monotone drawings of graphs

    Patrizio Angelini, Enrico Colasante, Giuseppe Di Battista, Fabrizio Frati, and Maurizio Patrignani. Monotone drawings of graphs. J. Graph Algorithms Appl., 16(1):5–35, 2012. doi:10.7155/jgaa.00249

    work page doi:10.7155/jgaa.00249 2012

  5. [5]

    Monotone drawings of graphs with fixed embedding

    Patrizio Angelini, Walter Didimo, Stephen Kobourov, Tamara Mchedlidze, Vin- cenzo Roselli, Antonios Symvonis, and Stephen Wismath. Monotone drawings of graphs with fixed embedding. Algorithmica, 71:233–257, 2015. doi:10.1007/ s00453-013-9790-3

    work page 2015

  6. [6]

    An algorithm to construct greedy drawings of triangulations

    Patrizio Angelini, Fabrizio Frati, and Luca Grilli. An algorithm to construct greedy drawings of triangulations. J. Graph Algorithms Appl., 14(1):19–51, 2010. doi: 10.7155/jgaa.00197

    work page doi:10.7155/jgaa.00197 2010

  7. [7]

    Arkin, Robert Connelly, and Joseph S

    Esther M. Arkin, Robert Connelly, and Joseph S. B. Mitchell. On monotone paths among obstacles with applications to planning assemblies. In Proc. 5th Ann. ACM Symp. Comput. Geom. (SoCG), pages 334–343, 1989. doi:10.1145/73833.73870

    work page arXiv 1989

  8. [8]

    Ex- ploring increasing-chord paths and trees

    Yeganeh Bahoo, Stephane Durocher, Sahar Mehrpour, and Debajyoti Mondal. Ex- ploring increasing-chord paths and trees. In Joachim Gudmundsson and Michiel Smid, editors, Proc. 29th Canadian Conf. Comput. Geometry (CCCG), pages 19– 24, 2017

    work page 2017

Show all 59 references
  1. [9]

    (Weakly) Self-approaching geometric graphs and spanners

    Davood Bakhshesh and Mohammad Farshi. (Weakly) Self-approaching geometric graphs and spanners. Comput. Geom., 78:20–36, 2019. doi:10.1016/j.comgeo. 2018.10.002

    2019 doi

  2. [10]

    Angle-monotonicity of Delaunay trian- gulation

    Davood Bakhshesh and Mohammad Farshi. Angle-monotonicity of Delaunay trian- gulation. Comput. Geom., 94:101711, 2021. doi:10.1016/j.comgeo.2020.101711

    2021

  3. [11]

    On the plane angle-monotone graphs

    Davood Bakhshesh and Mohammad Farshi. On the plane angle-monotone graphs. Comput. Geom., 100:101818, 2022. doi:10.1016/j.comgeo.2021.101818

    2022

  4. [12]

    Gabriel triangulations and angle-monotone graphs: Local routing and recognition

    Nicolas Bonichon, Prosenjit Bose, Paz Carmi, Irina Kostitsyna, Anna Lubiw, and Sander Verdonschot. Gabriel triangulations and angle-monotone graphs: Local routing and recognition. In Yifan Hu and Martin N¨ ollenburg, editors, Proc. Int. Symp Graph Drawing & Network Vis. (GD), ...

    2016 doi

  5. [13]

    Bernard Chazelle and David P. Dobkin. Intersection of convex objects in two and three dimensions. J. ACM, 34(1):1–27, 1987. doi:10.1145/7531.24036

    1987

  6. [14]

    Algorithms for updating minimal spanning trees

    Francis Chin and David Houck. Algorithms for updating minimal spanning trees. J. Comput. Syst. Sci., 16(3):333–344, 1978. doi:10.1016/0022-0000(78)90022-3

    1978 doi

  7. [15]

    Increasing- chord graphs on point sets

    Hooman Reisi Dehkordi, Fabrizio Frati, and Joachim Gudmundsson. Increasing- chord graphs on point sets. In Christian Duncan and Antonios Symvonis, editors, Proc. Int. Symp. Graph Drawing (GD), volume 8871 of LNCS, pages 464–475. Springer, 2014. doi:10.1007/978-3-662-45803-7_39...

    2014 doi

  8. [16]

    Greedy drawings of triangulations

    Raghavan Dhandapani. Greedy drawings of triangulations. Discrete. Comput. Geom., 43:375–392, 2010. doi:10.1007/s00454-009-9235-6

    2010 doi

  9. [17]

    Upward graph drawing

    Walter Didimo. Upward graph drawing. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 2308–2312. Springer, 2016. doi:10.1007/978-1-4939-2864-4\ _653

    2016 doi

  10. [18]

    Finding the k smallest spanning trees

    David Eppstein. Finding the k smallest spanning trees. BIT, 32:237–248, 1992. doi:10.1007/BF01994879

    1992 doi

  11. [19]

    Spanning trees and spanners

    David Eppstein. Spanning trees and spanners. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 425–461. North-Holland, Amsterdam,

  12. [20]

    Strongly monotone drawings of planar graphs

    Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze, and Manfred Scheucher. Strongly monotone drawings of planar graphs. In S´ andor Fekete and Anna Lubiw, editors,Proc. 32nd Int. Symp. Comput. Geom. (SoCG), volume 51 of LIPIcs, pages 37:1...

    2016 doi

  13. [21]

    The Euclidean degree-4 minimum span- ning tree problem is NP-hard

    Andrea Francke and Michael Hoffmann. The Euclidean degree-4 minimum span- ning tree problem is NP-hard. In Proc. 25th Ann. ACM Symp. Comput. Geom. (SoCG), pages 179–188, 2009. doi:10.1145/1542362.1542399

    2009

  14. [22]

    Frederickson

    Greg N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput., 26(2):484–538, 1997. doi: 10.1137/S0097539792226825

    1997 doi

  15. [23]

    Harold N. Gabow. Two algorithms for generating weighted spanning trees in order. SIAM J. Comput., 6:139–150, 1977. doi:10.1137/0206011

    1977 doi

  16. [24]

    Upward planarity testing

    Ashim Garg and Roberto Tamassia. Upward planarity testing. Order, 12(2):109– 133, 1995. doi:10.1007/BF01108622

    1995 doi

  17. [25]

    Papadimitriou

    George Georgakopoulos and Christos H. Papadimitriou. The 1-Steiner tree prob- lem. J. Algorithms, 8(1):122–130, 1987. doi:10.1016/0196-6774(87)90032-0

    1987 doi

  18. [26]

    Goodman and Richard Pollack

    Jacob E. Goodman and Richard Pollack. On the combinatorial classification of nondegenerate configurations in the plane. J. Combin. Theory Ser. A, 29(2):220– 235, 1980. doi:10.1016/0097-3165(80)90011-4

    1980 doi

  19. [27]

    Graham and Pavol Hell

    Ronald L. Graham and Pavol Hell. On the history of the minimum spanning tree problem. Ann. Hist. Comput., 7(1):43–57, 1985. doi:10.1109/MAHC.1985.10011

    1985

  20. [28]

    The number of homeomorphically irreducible trees, and other species

    Frank Harary and Geert Prins. The number of homeomorphically irreducible trees, and other species. Acta Math., 101(1–2):141–162, 1959. doi:10.1007/BF02559543

    1959 doi

  21. [29]

    Robinson, and Allen J

    Frank Harary, Robert W. Robinson, and Allen J. Schwenk. Twenty-step algorithm for determining the asymptotic number of trees of various species. J. Austral. Math. Soc., 20(4):483–503, 1975. doi:10.1017/S1446788700016190

    1975 doi

  22. [30]

    Optimal monotone drawings of trees

    Dayu He and Xin He. Optimal monotone drawings of trees. SIAM J. Discrete Math., 31(3):1867–1877, 2017. doi:10.1137/16M1080045

    2017 doi

  23. [31]

    Monotone drawings of 3-connected plane graphs

    Xin He and Dayu He. Monotone drawings of 3-connected plane graphs. In Nikhil Bansal and Irene Finocchi, editors, Proc. Europ. Symp. Algorithms (ESA), volume 9294 of LNCS, pages 729–741. Springer, 2015. doi:10.1007/978-3-662-48350-3_ 61

    2015 doi

  24. [32]

    Iqbal Hossain and Md

    Md. Iqbal Hossain and Md. Saidur Rahman. Good spanning trees in graph drawing. Theoret. Comput. Sci., 607:149–165, 2015. doi:10.1016/j.tcs.2015.09.004

    2015 doi

  25. [33]

    On monotone drawings of trees

    Philipp Kindermann, Andr´ e Schulz, Joachim Spoerhase, and Alexander Wolff. On monotone drawings of trees. In Christian Duncan and Antonios Symvonis, editors, Proc. Int. Symp. Graph Drawing (GD), volume 8871 of LNCS, pages 488–500. Springer, 2014. doi:10.1007/978-3-662-45803-7_41

    2014 doi

  26. [34]

    Michael P. Knapp. Sines and cosines of angles in arithmetic progression. Mathe- matics Magazine, 82(5):371–372, 2009. doi:10.4169/002557009X478436. Minimum Monotone Spanning Trees 15

    2009 doi

  27. [35]

    Luccio, and Franco P

    Hsiang-Tsung Kung, Fabrizio L. Luccio, and Franco P. Preparata. On finding the maxima of a set of vectors. J. ACM, 22(4):469–476, 1975. doi:10.1145/321906. 321910

    1975 doi

  28. [36]

    Construction and local routing for angle- monotone graphs

    Anna Lubiw and Debajyoti Mondal. Construction and local routing for angle- monotone graphs. J. Graph Algorithms Appl., 23(2):345–369, 2019. doi:10.7155/ jgaa.00494

    2019

  29. [37]

    Uniform 2d-monotone minimum spanning graphs

    Konstantinos Mastakas. Uniform 2d-monotone minimum spanning graphs. In Stephane Durocher and Shahin Kamali, editors, Proc 30th Canadian Conf. Com- put. Geom. (CCCG), pages 318–325, 2018. URL: https://arxiv.org/abs/1806. 08770

    2018

  30. [38]

    Drawing a rooted tree as a rooted y-monotone minimum spanning tree

    Konstantinos Mastakas. Drawing a rooted tree as a rooted y-monotone minimum spanning tree. Inform. Process. Lett., 166:106035, 2021. doi:10.1016/j.ipl. 2020.106035

    2021

  31. [39]

    On the construction of increasing- chord graphs on convex point sets

    Konstantinos Mastakas and Antonios Symvonis. On the construction of increasing- chord graphs on convex point sets. In Proc. 6th Int. Conf. Inform. Intell. Syst. Appl. (IISA), pages 1–6, 2015. doi:10.1109/IISA.2015.7388028

    2015

  32. [40]

    Rooted uniform monotone min- imum spanning trees

    Konstantinos Mastakas and Antonios Symvonis. Rooted uniform monotone min- imum spanning trees. In Dimitris Fotakis, Aris Pagourtzis, and Vangelis Th. Paschos, editors, Proc. Int. Conf. Algorithms & Complexity (CIAC), volume 10236 of LNCS, pages 405–417. Springer, 2017. doi:10....

    2017 doi

  33. [41]

    Mitrinovi´ c

    Dragoslav S. Mitrinovi´ c. Analytic Inequalities. Springer, 1970. doi:10.1007/ 978-3-642-99970-3

    1970

  34. [42]

    On self-approaching and increasing-chord drawings of 3-connected planar graphs

    Martin N¨ ollenburg, Roman Prutkin, and Ignaz Rutter. On self-approaching and increasing-chord drawings of 3-connected planar graphs. J. Comput. Geom., 7(1):47–69, 2016. doi:10.20382/jocg.v7i1a3

    2016 doi

  35. [43]

    Simple compact monotone tree drawings

    Anargyros Oikonomou and Antonios Symvonis. Simple compact monotone tree drawings. In Fabrizio Frati and Kwan-Liu Ma, editors,Proc. 25th Int. Symp. Graph Drawing & Netw. Vis. (GD), volume 10692 of LNCS, pages 326–333. Springer,

  36. [44]

    Monotone drawings of k-inner planar graphs

    Anargyros Oikonomou and Antonios Symvonis. Monotone drawings of k-inner planar graphs. In Therese Biedl and Andreas Kerren, editors, Proc. 26th Int. Symp. Graph Drawing & Netw. Vis. (GD), volume 11282 of LNCS, pages 347–353. Springer, 2018. doi:10.1007/978-3-030-04414-5_24

    2018 doi

  37. [45]

    Papadimitriou and David Ratajczak

    Christos H. Papadimitriou and David Ratajczak. On a conjecture related to ge- ometric routing. Theor. Comput. Sci., 344(1):3–14, 2005. doi:10.1016/j.tcs. 2005.06.022

    2005 doi

  38. [46]

    Papadimitriou and Umesh V

    Christos H. Papadimitriou and Umesh V. Vazirani. On two geometric problems related to the travelling salesman problem. J. Algorithms, 5(2):231–246, 1984. doi:10.1016/0196-6774(84)90029-4

    1984 doi

  39. [47]

    Geographic routing without location information

    Ananth Rao, Sylvia Ratnasamy, Christos Papadimitriou, Scott Shenker, and Ion Stoica. Geographic routing without location information. In Proc. 9th Ann. ACM Conf. Mobile Comput. Network. (MobiCom), pages 96–108, 2003. doi:10.1145/ 938985.938996

    2003

  40. [48]

    Geometric minimum diameter minimum cost spanning tree problem

    Dae Young Seo, Der-Tsai Lee, and Tien-Ching Lin. Geometric minimum diameter minimum cost spanning tree problem. In Proc. 20th Int. Symp. Algorithms & Com- put. (ISAAC), page 283–292. Springer, 2009. doi:10.1007/978-3-642-10631-6\ _30

    2009 doi

  41. [49]

    Closest-point problems

    Michael Ian Shamos and Dan Hoey. Closest-point problems. In Proc. 16th Ann. IEEE Symp. Foundat. Comput. Sci. (FOCS), pages 151–162, 1975. doi:10.1109/ SFCS.1975.8. 16 Di Giacomo, Didimo, Katsanou, Schlipf, Symvonis, and Wolff

    1975

  42. [50]

    P. M. Spira and A. Pan. On finding and updating spanning trees and shortest paths. SIAM J. Comput., 4(3):375–380, 1975. doi:10.1137/0204032. Minimum Monotone Spanning Trees 17 A Additional Material for Section 3 Lemma 1 (⋆). Let S be a set of points, and let P = ⟨u, x, v⟩ be a...

    1975 doi

  43. [53]

    A D-path is simply a path; clearly it must be d1-monotone or d2-monotone

  44. [54]

    By Theorem 1(ii), each leaf path lies in a distinct wedge of WD(v)

    A single-degree-4 D-tree consists of a degree-4 vertex v and four leaf paths emanating from v. By Theorem 1(ii), each leaf path lies in a distinct wedge of WD(v). Since every wedge is bounded by both d1 and d2, Corollary 1 ensures that each leaf path is both d1- and d2-monotone

  45. [55]

    A single-degree-3 D-tree consists of a degree-3 vertex v and three paths emanating from v such that, for some i ∈ {0, 1, 2, 3}, one path lies in the wedge Wi(v) and one in Wi+1(v), these two paths are both d1- and d2- monotone, and the third path connects all points in Wi+2(v)...

  46. [56]

    A double-degree-3 D-tree consists of two degree-3 vertices u and v and five paths such that, for somei ∈ {0, 1, 2, 3}, one path lies inWi(u), one in Wi+1(u), one in Wi+2(v), and one in Wi+3(v); these four paths are both d1- and d2-monotone, and the fifth path connects all poin...

  47. [57]

    If qy < m′ y, then q fails the test because the points m and m′ both dominate it directly; see Fig. 15a. Set the flag of q to false. Minimum Monotone Spanning Trees 27 m m′ q (a) qy < m′ y (< my) m m′ q (b) m′ y < qy < my p m r q (c) (m′ y <) my < qy Fig. 15:The three cases th...

  48. [58]

    If m′ y < qy < my, then set the flag of q to true, establish a pointer from q to m, and set m = q; see Fig. 15b

  49. [59]

    If my < qy, then we follow pointers from m to its successors as long as the current point is below q; see Fig. 15c. If the last such point p has a pointer to a point r in W1(q), establish a pointer from q to r. Independently of that, set the flag of q to true, set m = q, and s...

  50. [2000]

    doi:10.1016/B978-044482537-7/50010-3

    doi

  51. [2017]

    doi:10.1007/978-3-319-73915-1_26

    doi

Pith tools

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