Pith. sign in

REVIEW 4 major objections 3 minor 25 references

The Parameterized Complexity of Computing the Linear Vertex Arboricity

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

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

Pith's one-line read The paper proves that deciding whether a graph's vertices can be split into two path-forests is NP-hard even for graphs of maximum degree 5, that this threshold is tight, and that the problem parameterized by treewidth is fixed-parameter…

desk verdict Tight degree-5 hardness for linear vertex arboricity is likely correct, but a load-bearing typo in the variable gadget makes the main construction unverifiable as written. read the letter →

arxiv 2505.18885 v1 pith:EMB7META submitted 2025-05-24 cs.CC

Alexander Erhardt , Alexander Wolff This is my paper · ORCID
classification cs.CC MSC 05C8568Q1768Q27
keywords linearvertexarboricityweaklinecovernumberparameterizedcomplexityNP-hardnessmaximumdegreetreewidthfixed-parametertractabilityplanargraphs
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

The paper studies how hard it is to decide whether a graph's vertices can be partitioned into few parts so that each part induces a linear forest — a disjoint union of paths. This number, the linear vertex arboricity, coincides with the minimum number of straight lines needed to cover the vertices of a crossing-free drawing in three dimensions, so its complexity controls a natural measure of drawing visual complexity. The paper establishes that the decision problem for two parts is NP-hard already for graphs of maximum degree 5, and that this is best possible: every graph of maximum degree at most 4, except $K_5$, is already known to have linear vertex arboricity at most 2. For planar graphs the same problem is NP-hard at maximum degree 6, leaving the degree-5 planar case open. On the positive side, for every fixed $k$, deciding whether the linear vertex arboricity is at most $k$ is fixed-parameter tractable with respect to treewidth, via a monadic second-order logic formulation.

What carries the argument

The machinery is a set of forcing gadgets. The degree-5 reduction is built on the graph $K_5^-$, obtained from $K_5$ by deleting one edge; in any legal 2-coloring its two degree-3 vertices share a color, and exactly one of the remaining triangle vertices shares that color. Variable gadgets, clause gadgets, linking gadgets, and a starter gadget are assembled from copies of this block so that the terminals labeled 0 all receive the same color, each variable's two literal vertices are forced to be equal and opposite to its negation vertex, and each clause's literal vertices cannot all have the wrong color. A satisfying assignment therefore corresponds exactly to a legal 2-coloring of the entire graph. The planar reduction uses a larger seven-vertex triangulated block $B$ with the same forcing behavior. For the treewidth result, the mechanism is a monadic second-order logic (MSO2) formula — logic with quantification over vertex and edge sets — whose predicates express 'connected set', 'set inducing a cycle', 'set containing a star', and 'path forest', and which triggers the metatheorem that MSO2-definable properties are decidable in linear time on bounded-treewidth graphs.

What would settle it

Run an exhaustive search over all 2-colorings of the seven-vertex block $B$, and of the degree-5 variable gadget $V'_a$, with the anchor vertex fixed, and test each color class for the defining property of a linear forest. The paper's Lemmas 1 and 4 predict exactly one legal coloring in each case; any additional legal coloring — for instance, a coloring of $V'_a$ in which the two $a$-labeled vertices receive different colors — would refute the uniqueness lemmas on which the degree-5 reduction relies.

Watch

Extended reading notes

Core claim

The paper's central discovery is a sharp complexity threshold at maximum degree 5. It proves that the decision problem $2$-Lva, asking whether the vertices can be colored with two colors so that each color class induces a linear forest, is NP-hard even when the input graph has maximum degree 5, by a polynomial-time reduction from a planar bounded 3-SAT variant. The threshold is tight in a strong sense: a known degree bound shows that every graph of maximum degree at most 4, with the single exception of $K_5$, has linear vertex arboricity at most 2, so those instances are trivially decidable. For planar graphs the reduction gives NP-hardness at maximum degree 6 and leaves degree 5 open. The paper also proves that for every fixed $k$, deciding whether the linear vertex arboricity is at most $k$ is fixed-parameter tractable with respect to treewidth, by expressing the condition as a monadic second-order logic formula and invoking the corresponding linear-time metatheorem.

Load-bearing premise

The reductions stand or fall on the claims that each gadget admits exactly one legal two-coloring once an anchor vertex is fixed; those claims are verified by case analysis on diagrams, with some cases handled by symmetry, so any unlisted alternative coloring would break the equivalence between the formula and the graph.

Editorial extensions

If this is right

  • The exact value of the linear vertex arboricity is NP-hard to compute for graphs of maximum degree 5, because even distinguishing 2 from larger values is hard.
  • For graphs of maximum degree at most 4, 2-Lva is trivial: every such graph except $K_5$ is a yes-instance, and $K_5$ is the sole no-instance.
  • The para-NP-hardness with respect to maximum degree rules out any fixed-parameter algorithm for $k$-Lva parameterized by maximum degree, even for the constant $k = 2$, unless P equals NP.
  • For every fixed $k$, $k$-Lva is decidable in linear time on any graph class of bounded treewidth, with the running time depending only on treewidth and $k$ through a computable function.
  • For planar graphs, the maximum-degree-6 case is NP-hard, while the maximum-degree-5 case remains open; the authors report that a computer search found no 3-connected planar graph up to 12 vertices with maximum degree 5 that requires more than two colors.

Reading between the lines

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

  • Editorial extension: The planar degree-5 gap may be closable with a different link or starter gadget, because the degree-6 planar reduction becomes degree-6 only in specific connection points.
  • Editorial extension: The MSO2 formula is short once $k$ is fixed, so an explicit dynamic program over a tree decomposition with an elementary running time is likely attainable for $k$-Lva.
  • Editorial extension: Because of the known equality between linear vertex arboricity and the 3D weak line cover number, the hardness results transfer to deciding whether a graph can be drawn crossing-free in three dimensions with its vertices covered by two straight lines.
  • Editorial extension: The same $K_5^-$ forcing block might yield hardness for other degree-bounded vertex-partition problems that forbid a fixed forest-like induced subgraph, although the paper does not explore that direction.
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

4 major / 3 minor

Summary. The paper studies the linear vertex arboricity (lva) of a graph, focusing on the parameterized complexity of the decision problem k-LVA. It claims three main results: (i) 2-LVA is NP-hard for planar graphs of maximum degree 6; (ii) 2-LVA is NP-hard for general graphs of maximum degree 5, which would be tight because all graphs of maximum degree 4 except K5 have lva at most 2; and (iii) for any k, k-LVA is fixed-parameter tractable with respect to the treewidth of the input graph, proved via an MSO2 formulation and Courcelle's theorem. The paper also gives ILP and SAT formulations for k-LVA and leaves open the planar maximum-degree-5 case.

Significance. The maximum-degree-5 hardness result is the headline contribution: it would pin down the exact degree threshold at which 2-LVA becomes NP-hard and would complement the known polynomial behavior for maximum degree 4. The treewidth FPT result is a straightforward but solid application of Courcelle's theorem, and the ILP/SAT encodings are compact and potentially useful in practice. However, the degree-5 result is currently not verifiable because the variable-gadget construction in Section 3 is internally inconsistent and the gadget uniqueness proofs are not sufficiently rigorous. The planar degree-6 hardness and the FPT result appear sound, but the central tight-hardness claim needs substantial repair before the paper can be accepted.

major comments (4)
  1. [Section 3, variable gadget description and Lemma 4] The construction text and the proof of Lemma 4 describe incompatible graphs. The text says: 'add two nonadjacent vertices labeled a and connect both of them to both vertices 1 and 2. Next we connect the top a-labeled vertex to vertex 3 and the bottom one to vertex 5.' Under this literal reading, each of vertices 1 and 2 has degree at least 7 (three neighbors inside K5^-, plus 6 and 7, plus the two a-vertices), contradicting the claimed maximum degree 5 of H'. Lemma 4's proof, however, treats the upper a-vertex as adjacent to vertices 3, 6, and 7, and the lower a-vertex as forming a triangle with 6 and 7, which corresponds to attaching the a-vertices to 6 and 7, not to 1 and 2. Since Lemma 4 supplies the uniqueness and color-forcing properties used in the correctness proof of Theorem 2, the reduction cannot be checked as written and the degree bound is not established until the intended adjacency is specified and Lemma 4 is re-proved for that graph.
  2. [Section 3, Lemma 4 proof] Even setting aside the construction mismatch, the uniqueness proof is incomplete. The step 'the neighbors of that vertex (i.e., vertices 3, 6, and 7) must all be gray' does not follow from the two stated rules alone: a vertex with three same-colored neighbors is forbidden only if the vertex itself has that color, and here the upper a-vertex is assumed white; additional structural arguments are needed to rule out each neighbor being white. Similarly, the assertion 'this forces vertex 5 to be gray' is not justified by the stated rules, since if vertex 5 were white the lower a-vertex would have a bichromatic neighborhood (white neighbor 5, gray neighbors 6 and 7). The proof must give a complete case analysis with explicit adjacencies, or state and prove the automorphisms used in 'the other case is symmetric.' The same figure-dependent style appears in Lemmas 1, 2, 3, 5, and 6, so these proofs need to be made rigorous throughout.
  3. [Section 3, proof of Theorem 2] The proof begins by saying 'we again construct a planar graph H' using the planar embedding of H_phi as a pattern,' but the abstract and Section 6 explicitly leave the planar maximum-degree-5 case open, and the section's own opening says planarity is not needed. Taken literally, the sentence would assert a stronger result that contradicts the paper's stated open problem. The word 'planar' should be removed or replaced with a correct description of the constructed graph.
  4. [Section 3, degree bound in Theorem 2] The proof asserts that the resulting graph H' 'has maximum vertex degree 5' without any per-vertex degree count. In particular, the description of the linking pattern between clause gadgets is ambiguous: the text says each of the three linking vertices is connected to three 0-labeled vertices and that vertex 2 has two such neighbors on the left and one on the right, with vertices 1 and 3 'opposite,' but this does not specify how many linking vertices are incident to each individual 0-labeled vertex. A 0-labeled vertex in an internal clause gadget is already degree 2 inside its 5- or 6-cycle and may receive connections from both the left and right links; without an explicit adjacency specification one cannot verify that its degree never exceeds 5. The degree bound is a central claim of Theorem 2 and must be established by an explicit count.
minor comments (3)
  1. [Abstract] The sentence 'All graphs of maximum degree 4 (except for K4) have linear vertex arboricity at most 2' should say 'except for K5,' since K4 has maximum degree 3 and the introduction correctly identifies K5 as the only no-instance among graphs of maximum degree 4.
  2. [Section 4, MSO2 formulation] The formula named 'k-LVA(U)' is a sentence with no free variable U; this notation is confusing and should be changed. In addition, the proof of Theorem 4 should state explicitly that if the input value k is greater than tau+1, the answer is trivially yes, so the formula length can be bounded as a function of the treewidth tau; otherwise the formula length appears to depend on k as an input parameter.
  3. [Section 5, Equation (4)] Equation (4) is not symmetric in u and w but is written as a constraint 'for all {u,w} in E(G).' Since {u,w} is an unordered edge, the expression x_{u,v} + x_{v,w} checks only the orientation u < v < w and not w < v < u. Please state explicitly that the constraint is generated for both orientations (or for each ordered pair of adjacent vertices), otherwise the reverse ordering is not excluded.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: reductions use external NP-hard SAT variants, external bounds, and Courcelle's theorem; self-citations are background only.

full rationale

The central hardness proofs reduce from the externally proved NP-hard problem Clause-Linked-Planar-Exactly-3-Bounded-3-SAT [12], and the gadget lemmas are argued by direct case analysis. The tightness claim uses Matsumoto's bound [18], an external theorem, and the FPT result uses Courcelle's theorem [6,7] and Korhonen's treewidth approximation [16]; none of these are adapted to assume the target result. The equivalence between linear vertex arboricity and 3D weak line cover number [2] is background context, not a step in the reductions. The only self-references are to the first author's master's thesis [10] as the source of the shortened paper and to prior co-authored hardness results [2,3]; these are normal background citations, and the paper's new maximum-degree-5 and planar-degree-6 results do not reduce to them. The reported ambiguity in the Section 3 variable-gadget construction (text says the a-labeled vertices are connected to vertices 1 and 2, while Lemma 4's case analysis treats their neighbors as 3,6,7 and 6,7) is a correctness and presentation concern, not circularity: it does not make any predicted claim equivalent to its own input. No fitted parameter is renamed as a prediction, no uniqueness theorem is imported from the authors' prior work to force the choice of gadgets, and no known result is merely renamed as a new organization. The derivation chain is therefore self-contained with respect to the claims it makes; any weakness lies in verifiability of the gadget case analyses, not in circular dependence.

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

The central claims depend only on standard external results: the NP-hardness of the chosen SAT variant, Matsumoto's bound on linear vertex arboricity, Courcelle's meta-theorem, and the treewidth approximation algorithm. No free parameters or invented entities are introduced. The paper's own gadgets are constructions within the existing definitions.

assumptions (5)
  • standard math Courcelle's theorem: MSO2 model checking is fixed-parameter tractable with respect to treewidth and formula length.
    Used as a black box in Section 4 to obtain the FPT algorithm for k-Lva.
  • standard math Matsumoto's bound: lva(G) <= 1 + floor(Delta(G)/2), with equality characterization for even maximum degree.
    Used in Sections 1 and 3 to assert that max-degree-4 graphs except K5 have lva at most 2 and to justify properties of the K5-minus-edge gadget.
  • domain assumption Clause-Linked-Planar-Exactly-3-Bounded-3-SAT is NP-hard (Fellows et al.).
    Used as the source problem in the reductions in Sections 2 and 3.
  • standard math Korhonen's 2-approximation algorithm for treewidth.
    Mentioned in Section 4 to construct a tree decomposition in O(2^t * n) time; not needed for the correctness of the FPT result but used to make it algorithmic.
  • standard math MSO2 counting quantifiers, such as 'there exist exactly two' and 'there exist at least three', are expressible in monadic second-order logic.
    Used implicitly in the MSO2 predicates in Section 4 to define Cycle-Set and Star.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Parameterized Complexity of Computing the Linear Vertex Arboricity." pith.science (2026). https://pith.science/paper/EMB7META

@misc{pith2026250518885,
  author       = {Pith},
  title        = {Pith review of: The Parameterized Complexity of Computing the Linear Vertex Arboricity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EMB7META}},
  note         = {Machine review of arXiv:2505.18885}
}
abstract

The \emph{linear vertex arboricity} of a graph is the smallest number of sets into which the vertices of a graph can be partitioned so that each of these sets induces a linear forest. Chaplick et al. [JoCG 2020] showed that, somewhat surprisingly, the linear vertex arboricity of a graph is the same as the \emph{3D weak line cover number} of the graph, that is, the minimum number of straight lines necessary to cover the vertices of a crossing-free straight-line drawing of the graph in $\mathbb{R}^3$. Chaplick et al. [JGAA 2023] showed that deciding whether a given graph has linear vertex arboricity 2 is NP-hard. In this paper, we investigate the parameterized complexity of computing the linear vertex arboricity. We show that the problem is para-NP-hard with respect to the parameter maximum degree. Our result is tight in the following sense. All graphs of maximum degree 4 (except for $K_4$) have linear vertex arboricity at most 2, whereas we show that it is NP-hard to decide, given a graph of maximum degree 5, whether its linear vertex arboricity is 2. Moreover, we show that, for planar graphs, the same question is NP-hard for graphs of maximum degree 6, leaving open the maximum-degree-5 case. Finally, we prove that, for any $k \ge 1$, deciding whether the linear vertex arboricity of a graph is at most $k$ is fixed-parameter tractable with respect to the treewidth of the given graph.

Figures

Figures reproduced from arXiv: 2505.18885 by the authors.

Figure 1
Figure 1. The dodecahedron graph has 20 vertices and 30 edges (a), segment number 13, 2D strong line cover number 10 (b), 2D and 3D weak line cover number 2 [14] (c), arc number 10, and circle cover number 5 [17] (d). most √ 2n, whereas Eppstein [9] constructed, for every positive integer ℓ, a cubic 3-connected planar bipartite graph with O(ℓ 3 ) vertices and 2D weak line cover number greater than ℓ. A segment in a straight-l… view at source ↗
Figure 2
Figure 2. Basic building block B Lemma 1. Assuming that vertex 1 of B is gray, the unique legal coloring of B is as in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. We simply attach two white vertices (labeled [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: The gadgets for a two-variable clause a∨b (left) and for a three-variable clause a ∨ b ∨ c (right). Both use copies of the basic building block B. Proof. Assuming that the left 0-labeled vertex of the clause gadget is white, vertex 1 of the copy of B must be gray since…
Figure 5
Figure 5. Figure 5: The graph Hφ with black clause vertices and white variable vertices (see inset) and the resulting graph G for φ = (¯a ∨ ¯b) ∧ (a ∨ b ∨ c) ∧ (a ∨ c ∨ d) ∧ (¯c ∨ d) ∧ (b ∨ d¯) [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: The basic building block K − 5 1 2 3 4 5 6 7 a a a [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 8
Figure 8. Figure 8: Gadget for the clause a ∨ b ∨ c Lemma 5. Assuming that the three 0-labeled vertices of a clause gadget have the same color, those of the next clause gadget in the chain must have the same color. Proof. Assuming that the 0-labeled vertices of the left clause gadget (lig…
Figure 9
Figure 9. Figure 9: The starter gadget consists of three copies of K − 5 and a K2. It ensures that the 0-labeled vertices of the first clause gadget in the chain must receive the same color. vertices 3 and 5 must be white (otherwise they would have three neighbors in their own color), and…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 18 canonical work pages

  1. [1]

    Line and Plane Cover Numbers Revisited

    Therese Biedl, Stefan Felsner, Henk Meijer, and Alexander Wolff. Line and plane cover numbers revisited. In Daniel Archambault and Csaba D. T´ oth, editors, Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD), volume 11904 of LNCS, pages 409–415. Springer, 2019. URL: http://arxiv.org/abs/1908.07647, doi:10.1007/978-3-030-35802-0_31

    work page Pith review arXiv 2019

  2. [2]

    Drawing graphs on few lines and few planes

    Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbit- sky, and Alexander Wolff. Drawing graphs on few lines and few planes. J. Comput. Geom., 11(1):433–475, 2020. doi:10.20382/jocg.v11i1a17

    work page doi:10.20382/jocg.v11i1a17 2020

  3. [3]

    The complexity of drawing graphs on few lines and few planes

    Steven Chaplick, Krzysztof Fleszar, Fabian Lipp, Alexander Ravsky, Oleg Verbit- sky, and Alexander Wolff. The complexity of drawing graphs on few lines and few planes. J. Graph Algorithms Appl., 27(6):459–488, 2023. doi:10.7155/jgaa. 00630

    doi:10.7155/jgaa 2023

  4. [4]

    Beyond outerplanarity

    Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre L¨ offler, and Alexander Wolff. Beyond outerplanarity. In Fabrizio Frati and Kwan-Liu Ma, editors, Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD), volume 10692 of LNCS, page 546–559. Springer, 2018. URL: https://arxiv.org/abs/1708.08723, doi: 10.1007/978-3-319-73915-1\_42

    arXiv 2018

  5. [5]

    The Parametrized Complexity of the Segment Number

    Sabine Cornelsen, Giordano Da Lozzo, Luca Grilli, Siddharth Gupta, Jan Kra- tochv ´ ıl, and Alexander Wolff. The parametrized complexity of the segment number. In Michael Bekos and Markus Chimani, editors,Proc. 31st Int. Symp. Graph Draw- ing & Network Vis. (GD), volume 14466 of LNCS, pages 97–113. Springer, 2023. URL: https://arxiv.org/abs/2308.15416, do...

    work page Pith review arXiv 2023

  6. [6]

    The monadic second-order logic of graphs

    Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. & Comput., 85(1):12–75, 1990. doi:10.1016/0890-5401(90) 90043-H

    doi:10.1016/0890-5401(90 1990

  7. [7]

    Monadic second-order logic, page 315–426

    Bruno Courcelle and Joost Engelfriet. Monadic second-order logic, page 315–426. Encyclopedia of Mathematics and its Applications. Cambridge Univ. Press, 2012. doi:10.1017/CBO9780511977619.007

    work page doi:10.1017/cbo9780511977619.007 2012

  8. [8]

    Vida Dujmovi´ c, David Eppstein, Matthew Suderman, and David R. Wood. Draw- ings of planar graphs with few slopes and segments. Comput. Geom., 38:194–212,

    work page

Show all 25 references
  1. [9]

    Cubic planar graphs that cannot be drawn on few lines

    David Eppstein. Cubic planar graphs that cannot be drawn on few lines. J. Comput. Geom., 12(1):178–197, 2021. doi:10.20382/V12I1A8

    2021 doi

  2. [10]

    The weak line cover number in 3D for restricted graph classes

    Alexander Erhardt. The weak line cover number in 3D for restricted graph classes. Master’s thesis, Institut f¨ ur Informatik, Universit¨ at W¨ urzburg, 2021. In German. URL: https://www1.pub.informatik.uni-wuerzburg.de/pub/theses/ 2021-erhardt-masterarbeit.pdf

    2021

  3. [11]

    Vertex-partitioning into fixed additive induced-hereditary prop- erties is NP-hard

    Alastair Farrugia. Vertex-partitioning into fixed additive induced-hereditary prop- erties is NP-hard. Electr. J. Comb., 11(1), 2004. doi:10.37236/1799

    2004 doi

  4. [12]

    Fellows, Jan Kratochv ´ ıl, Matthias Middendorf, and Frank Pfeiffer

    Michael R. Fellows, Jan Kratochv ´ ıl, Matthias Middendorf, and Frank Pfeiffer. The complexity of induced minors and related problems. Algorithmica, 13:266–282,

  5. [13]

    4-connected triangulations on few lines

    Stefan Felsner. 4-connected triangulations on few lines. J. Comput. Geom., 11(1):476–492, 2020. doi:10.20382/JOCG.V11I1A18

    2020 doi

  6. [14]

    On the weak line cover numbers

    Oksana Firman, Alexander Ravsky, and Alexander Wolff. On the weak line cover numbers. In Matias Korman and Wolfgang Mulzer, editors, Proc. 34th Europ. Workshop Comput. Geom. (EuroCG), pages 63:1–5, 2018. URL: https: //conference.imp.fu-berlin.de/eurocg18/download/paper_63.pdf....

    2018

  7. [15]

    Experimental analy- sis of the accessibility of drawings with few segments

    Philipp Kindermann, Wouter Meulemans, and Andr´ e Schulz. Experimental analy- sis of the accessibility of drawings with few segments. J. Graph Algorithms Appl., 22(3):501–518, 2018. doi:10.7155/jgaa.00474

    2018 doi

  8. [16]

    A single-exponential time 2-approximation algorithm for treewidth

    Tuukka Korhonen. A single-exponential time 2-approximation algorithm for treewidth. SIAM J. Comput., pages FOCS21–174–FOCS21–194, to appear. doi: 10.1137/22M147551X

    doi

  9. [17]

    Drawing graphs on few circles and few spheres

    Myroslav Kryven, Alexander Ravsky, and Alexander Wolff. Drawing graphs on few circles and few spheres. J. Graph Algorithms Appl., 23(2):371–391, 2019. doi: 10.7155/jgaa.00495

    2019 doi

  10. [18]

    Bounds for the vertex linear arboricity

    Makoto Matsumoto. Bounds for the vertex linear arboricity. J. Graph Theory, 14(1):117–126, 1990. doi:10.1002/jgt.3190140113

    1990 doi

  11. [19]

    Variants of the segment number of a graph

    Yoshio Okamoto, Alexander Ravsky, and Alexander Wolff. Variants of the segment number of a graph. In Daniel Archambault and Csaba D. T´ oth, editors, Proc. 27th Int. Symp. Graph Drawing & Network Vis. (GD), volume 11904 of LNCS, pages 430–443. Springer, 2019. URL: http://arxiv...

    2019 arXiv

  12. [20]

    On the computational complexity and geometry of the first-order theory of the reals

    James Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi- algebraic sets. The decision problem for the existential theory of the reals. J. Symb. Comput., 13(3):255–299, 1992. d...

    1992 doi

  13. [21]

    On the computational complexity and geometry of the first- order theory of the reals

    James Renegar. On the computational complexity and geometry of the first- order theory of the reals. Part II: The general decision problem. Preliminar- ies for quantifier elimination. J. Symb. Comput., 13(3):301–327, 1992. doi: 10.1016/S0747-7171(10)80004-5

    1992 doi

  14. [22]

    On the computational complexity and geometry of the first-order theory of the reals

    James Renegar. On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier elimination. J. Symb. Comput., 13(3):329– 352, 1992. doi:10.1016/S0747-7171(10)80005-7

    1992 doi

  15. [23]

    Drawing graphs with few arcs

    Andr´ e Schulz. Drawing graphs with few arcs. J. Graph Algorithms Appl., 19(1):393–412, 2015. doi:10.7155/jgaa.00366

    2015 doi

  16. [1995]

    doi:10.1007/BF01190507

    doi

  17. [2007]

    doi:10.1016/j.comgeo.2006.09.002

    2006 doi

Pith tools

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