Pith. sign in

REVIEW 3 major objections 4 minor 43 references

Pathways to Tractability for Geometric Thickness

T0 review · 3 major / 4 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 Computing geometric thickness becomes fixed-parameter tractable for two structural parameters, and the extension problem is NP-hard with only two missing vertices.

desk verdict First parameterized algorithms for geometric thickness, with a solid FPT core; the extension XP upper bound has a real gap that needs a fix. read the letter →

arxiv 2411.15864 v1 pith:NYGGVV3F submitted 2024-11-24 cs.CC cs.CG

Thomas Depian , Simon Dominik Fink , Alexander Firbas , Robert Ganian , Martin Nöllenburg This is my paper · ORCID
classification cs.CCcs.CG
keywords geometricthicknessstraight-linedrawingsparameterizedcomplexitykernelizationvertexcovernumberfeedbackedgedrawingextensionW[1]-hardness
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 studies geometric thickness: the smallest number of crossing-free layers into which the edges of a straight-line drawing of a graph can be split. Because recognizing graphs of geometric thickness 2 is NP-hard, the authors ask which small structural parameters restore tractability, and they prove two fixed-parameter algorithms: one parameterized by the vertex cover number and one by the feedback edge number, both via kernels that shrink the instance to bounded size. For the natural extension problem, in which a partially drawn and edge-colored solution must be completed, they prove a complete complexity map: adding only $k$ missing edges is fixed-parameter tractable, adding $k$ missing vertices and edges together is XP-tractable but W[1]-hard, and already deleting just two vertices makes the problem NP-hard. These are the first parameterized algorithms for geometric thickness, and they locate exactly where the problem's intractability begins.

What carries the argument

For the vertex-cover result the central object is the clone: two vertices outside the cover with identical neighborhoods and identically colored incident edges. Lemma 1 characterizes exactly when such a clone can be reinserted into its cell without creating a monochromatic crossing, and Lemma 2 combines that characterization with a bound on the number of cells induced by the cover and a pigeonhole argument to show that a large equivalence class of twins can always be shrunk. For the feedback-edge result the mechanism is a long path of degree-2 vertices drawn as a subdivided straight segment: if a path is much longer than the rest of the drawing, its subdivisions can absorb every monochromatic crossing, so the whole path can be removed. The hardness results are carried by choice gadgets, small red-triangle arrangements around anchor vertices that confine a missing vertex to one of several tiny disjoint disks, which the paper assembles around a regular $k$-gon with blocking edges to encode Multicolored Clique, and then reuses on a square with two stars whose edge colors must be disjoint for the two-vertex NP-hardness.

What would settle it

Take the two-vertex reduction for a tiny unsatisfiable 3-SAT formula, such as the conjunction of $x$ and $\neg x$, and solve the resulting Geometric Thickness Extension instance exactly by algebraic or exhaustive-rational means. The reduction claims the instance is negative; if a valid geometric extension is found, the proof of Theorem 5 fails at Lemma 10.

Watch

Extended reading notes

Core claim

The paper's own claims are: Geometric Thickness is fixed-parameter tractable when parameterized by the vertex cover number (Theorem 1) and by the feedback edge number (Theorem 2), with kernels of size $\ell^{O(k)}$ and $O(10^k \cdot 81^k)$ respectively. Geometric Thickness Extension is fixed-parameter tractable when only $k$ edges are missing (Theorem 3), is XP-tractable and W[1]-hard when $k$ counts both missing vertices and missing edges (Theorem 4), and is NP-hard even when exactly two vertices are missing from the provided partial drawing (Theorem 5). The W[1]-hardness of Theorem 4 holds even when the total number of layers is included in the parameter, and the two-vertex hardness is meant as a sharp contrast to earlier FPT results for extending other classes of drawings.

Load-bearing premise

The load-bearing premise is that the two-vertex NP-hardness construction really forces the two missing vertices into their intended regions and, crucially, that in every valid extension the color sets used by the truth-assignment star and the verification star are disjoint, which the paper only justifies with a proof sketch.

Editorial extensions

If this is right

  • If Theorem 1 is right, geometric thickness can be computed in time $f(k)n^{O(1)}$ for every graph whose vertex cover number $k$ is small, giving the first FPT algorithm for the problem.
  • If Theorem 2 is right, the same holds for graphs with small feedback edge number, a complementary structural parameter.
  • If Theorem 3 is right, any layered straight-line drawing missing at most $k$ edges can be completed in time $k^k n$, regardless of the number of layers.
  • If Theorem 4 is right, no FPT algorithm exists for completing drawings with $k$ missing vertices and edges unless FPT = W[1], even when the number of layers is added to the parameter.
  • If Theorem 5 is right, every algorithm parameterized by the number of missing vertices is ruled out unless P = NP, since the problem is hard already for two missing vertices.

Reading between the lines

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

  • My inference: the choice-gadget machinery is not thickness-specific, so the same red-triangle blocking and disjoint-color argument may transfer to other geometric drawing-extension problems with layer or color constraints.
  • My inference: the vertex-cover kernel's dependence on $\ell^{O(k)}$ comes from the cell-count bound; if that bound can be improved, the kernel could become independent of the number of layers, which would make Theorem 1 more directly usable.
  • My inference: the two-vertex NP-hardness leaves open whether the problem is $\exists\mathbb{R}$-complete; if the ETR formulation from Lemma 5 can handle pre-drawn vertices in the same way, the hardness could be strengthened beyond NP-hardness.
  • My inference: because Theorem 4 stays W[1]-hard even when the layer count is part of the parameter, the authors' open combination of vertex-plus-edge deletion distance with the layer count appears to be the most promising remaining parameterization for an FPT result.
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 paper studies the parameterized complexity of computing geometric thickness (GT), where edges must be drawn as straight-line segments and partitioned into a minimum number of crossing-free layers. It contributes two FPT algorithms for GT, parameterized by vertex cover number (Theorem 1) and feedback edge number (Theorem 2), both obtained via kernelization. In the extension setting, it gives an FPT algorithm when only k edges are missing from a partial drawing (Theorem 3), an XP-algorithm plus W[1]-hardness when k edges and vertices are missing (Theorem 4), and NP-hardness when only two vertices are missing (Theorem 5). The paper thus claims a complete trichotomy for the extension problem depending on whether one parameterizes by missing edges, missing vertices, or both.

Significance. If the technical results are correct, this is a meaningful contribution: it provides the first parameterized algorithms for geometric thickness, a problem whose parameterized complexity had not been systematically addressed before. The extension-setting trichotomy is a clean and interesting structural result, and the FPT algorithm for missing edges is simple and elegant. The paper is largely self-contained, starting from explicit geometric characterizations and building the reductions from elementary constructions. The main results are false-or-true complexity statements with no fitted parameters, and the proofs of the two FPT kernelizations are plausibly correct modulo the issues below. The paper also identifies a natural open problem, GT parameterized by treewidth/treedepth, with a clear discussion of why standard dynamic-programming approaches fail. Provided the flagged technical gaps are repaired, the paper would merit publication.

major comments (3)
  1. [Section 4 (XP-membership proof of Theorem 4)] The deletion rule for F3 conjuncts with exactly one free variable and three collinear predetermined positions is unsound. Consider a missing vertex b, a predrawn edge cd, and a predrawn vertex a lying on the line through c and d between c and d, with new edge ab. The original test A(a,b,c)A(a,b,d)>0 ∨ A(c,d,a)A(c,d,b)>0 is exact in this degenerate case: the second term is zero, but the first term is negative exactly when a lies between c and d, so the conjunct is necessary to forbid coloring ab the same as cd. Deleting it can turn an unsatisfiable instance into a satisfiable one, because the relaxed formula may accept a vertex-edge crossing at a. The proof must replace the blanket deletion with a case analysis or with an exact segment-intersection predicate for collinear configurations; as written, the claimed XP-membership is not established.
  2. [Section 2, Lemma 2] The cell-count bound used in the pigeonhole argument appears to be incorrect. The definition of C_{Γ,S}(v) in Definition 2 uses the half-planes H(v,a,b) whose boundary lines are the C(k',2) lines through pairs of vertices of S, not the k' lines through individual vertices. The bound of (k'^2+k'+2)/2 cited from Theorem 28.1.1 of [31] is the number of cells in an arrangement of k' lines, whereas the relevant arrangement has C(k',2) lines and can have O(k'^4) cells. Since the reduction rule's threshold is set to exceed the claimed cell count, the proof of Lemma 2 as written is not valid. The kernel-size statement can likely be repaired by raising the threshold to ℓ^{k'}·O(k'^4), which still gives ℓ^{O(k)} vertices for ℓ≥2, but the correction needs to be made explicitly.
  3. [Section 7, Lemma 10] Property (iii) of Lemma 10, which asserts that the color sets of the truth-assignment star and the verification star are disjoint in every valid extension, is supported only by a proof sketch ('the edges of t ... cut through the square vertically ... the visibility is blocked'). Section 7.1 does not provide the missing geometric derivation. Since Property (iii) is the central mechanism that prevents a satisfying assignment from being invalidated by shared colors, the NP-hardness reduction depends on it. A complete coordinate-based or otherwise rigorous proof of this property is required.
minor comments (4)
  1. [Section 4] In the XP-membership proof of Theorem 4, the definition of m' reads m' := |V(G)| - |V(H)|, but it should be |E(G)| - |E(H)|, the number of missing edges.
  2. [Section 4] The displayed runtime equality (9·O(n^4))^{O((2n'+m')^2)} = L^{O(1)}·n^{O(k)} is not correct as written; the left-hand side gives n^{O(k^2)}, which is still an XP bound, but the equality should be adjusted.
  3. [Section 6.6] The proof of Lemma 8 is described mostly by a construction sketch with forbidden segments and a scaling factor; for a journal version, more formal justification that the forbidden-segment lengths and the chosen s0 indeed guarantee a non-degenerate placement of all global blocking edges would help.
  4. [Section 1.2 / Observation 3] Observation 3 states that the set of safe positions for moving a vertex is open, but the proof is deferred to the text; a short justification would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorems are derived from explicit geometric lemmas, and the few self-citations are stylistic rather than load-bearing.

full rationale

The paper's derivation chain is self-contained. Theorem 1 is built from the cloneability characterization (Observations 2 and 3, Lemma 1), a pigeonhole/kernel argument (Lemma 2), and the external Dujmovic-Wood treewidth bound [20]; no quantity is defined in terms of the result it is used to prove. Theorem 2's correctness rests on Lemma 4, which is proved directly by reinserting long paths as subdivided straight-line segments rather than by invoking the theorem or a self-citation. Theorem 3 is a simple branching/coloring argument with no circular dependence. The extension results in Theorems 4 and 5 are supported by an explicit ETR encoding (Lemma 5) and by explicit choice-gadget constructions with their own correctness lemmas (Lemmas 6-9), plus the 3-SAT reduction culminating in Lemma 10. The only self-citations are to Depian et al. [16], and the paper uses them as technique pointers ('geometric analogue of the technique of Depian et al. [16]', 'Similar to [16]'); it does not cite [16] as an authoritative theorem on which the current proofs depend. The constructions and correctness arguments are reproduced in the present paper rather than imported wholesale. The reviewer-noted concern about the XP proof's deletion of certain F3 conjuncts, and the proof-sketch status of Lemma 10, are correctness risks, not circularity: even if those arguments are incomplete, the claimed results are not forced by construction, by fitted parameters, or by a self-citation chain. No empirical fitting or renaming of known results occurs. Accordingly, the appropriate circularity score is 0.

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

No free parameters are fitted to data; the only construction-specific quantities, such as epsilon and the scaling factor s0, are chosen to make the reductions well-defined rather than to fit an output. The central claims rely on standard prior results listed above, including the Dujmovic-Wood treewidth bound, decidable ETR membership, and arrangement cell-count bounds.

assumptions (6)
  • domain assumption Every graph of treewidth at most k has geometric thickness at most ceil(k/2) (Dujmovic and Wood [20]).
    Invoked in the proof of Theorem 1 to bound the number of colors l by O(k) so the l^{O(k)} kernel yields fixed-parameter tractability.
  • domain assumption Geometric Thickness is in the Existential Theory of the Reals, hence decidable (Förster et al. [28]).
    Used to decide kernel instances in Lemma 2 and as the basis of the ETR formulation in Lemma 5.
  • standard math An arrangement-theoretic bound (Theorem 28.1.1 of [31]) limits the number of distinct cells induced by a vertex cover in a drawing.
    Used in the pigeonhole step of Lemma 2 to force two clones into the same cell. As noted in red flags, the explicit count appears to use an arrangement of k' lines rather than the C(k',2) lines through pairs of S; the asymptotic claim is unaffected.
  • domain assumption Every geometric l-layer drawing can be perturbed to general position without changing the number of colors (Observation 1).
    Folklore fact used throughout to justify collinearity and crossing assumptions in Lemma 1 and the ETR formula.
  • ad hoc to paper The W[1]-hardness and NP-hardness constructions can be scaled and perturbed so that all required visibility tunnels have positive length and the choice gadgets constrain vertices to the intended regions.
    Sections 6.5, 6.6 and 7.1 rely on choosing epsilon and a scaling factor s0 so that forbidden segments do not cover the whole segment; the trigonometric bounds are asserted rather than fully derived.
  • domain assumption The existential theory of the reals can be decided in subexponential time in the number of variables (Grigoryev and Vorobjov [32]).
    Used in the XP upper bound of Theorem 4.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pathways to Tractability for Geometric Thickness." pith.science (2026). https://pith.science/paper/NYGGVV3F

@misc{pith2026241115864,
  author       = {Pith},
  title        = {Pith review of: Pathways to Tractability for Geometric Thickness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NYGGVV3F}},
  note         = {Machine review of arXiv:2411.15864}
}
read the original abstract

We study the classical problem of computing geometric thickness, i.e., finding a straight-line drawing of an input graph and a partition of its edges into as few parts as possible so that each part is crossing-free. Since the problem is NP-hard, we investigate its tractability through the lens of parameterized complexity. As our first set of contributions, we provide two fixed-parameter algorithms which utilize well-studied parameters of the input graph, notably the vertex cover and feedback edge numbers. Since parameterizing by the thickness itself does not yield tractability and the use of other structural parameters remains open due to general challenges identified in previous works, as our second set of contributions, we propose a different pathway to tractability for the problem: extension of partial solutions. In particular, we establish a full characterization of the problem's parameterized complexity in the extension setting depending on whether we parameterize by the number of missing vertices, edges, or both.

Figures

Figures reproduced from arXiv: 2411.15864 by the authors.

Figure 1
Figure 1. Illustration of Definition 1. of the class. Clearly, deleting a vertex preserves positive instances. Conversely, in a drawing of the instance without x, using the pigeon-hole principle, we will always be able to find at least two mutual clones c1, c2 of x’s class that share a cell. Using our characterization, this will imply that c1 can be cloned within that cell, i.e., x can always be re-inserted into the drawing, … view at source ↗
Figure 2
Figure 2. Illustrations for Observation 2 (left), Observation 3 (middle, the gray area is the complement of B), and Definition 2 (right, the set S is shown in blue, the cells of Γ induced by S are shown in gray). Observation 3 Let G be a graph, (Γ, χ) be a geometric ℓ-layer drawing of G in general position, and v ∈ V (G). Then, the set B ⊆ R 2 where v can be moved to in (Γ, χ) without introducing monochromatic crossings, is o… view at source ↗
Figure 3
Figure 3. A graph G ′ without degree one and zero vertices (left), a corresponding feedback edge set F and forest T as well as the vertex set C (middle), and the graph G0 (right). 3 Parameterizing by the Feedback Edge Set Number In this section, we show that GT is also fixed-parameter tractable when param￾eterized by the feedback edge number (Theorem 2). Our proof strategy is as follows: After some trivial preprocessing steps… view at source ↗
Figures from the paper (12 more)
Figure 4
Figure 4. Figure 4: The drawing (Γ ′ i , χ′ i) with Pi+1 represented as a single red edge (left), and (Γi+1, χi+1) with resolved crossings and Pi+1 fully drawn (right). In this example, one red crossing needed to be resolved and Pi+1 contains 3 internal vertices, hence one additional subd…
Figure 5
Figure 5. Figure 5: An instance (X, k = 3) of Multicolored Clique (left), the resulting instance of GTE where crosses denote possible vertex positions and non-edges of X are drawn as dashed lines (middle), and a valid extension showing that X contains a K3 (right). r i 1 r i 2 r i 3 a i r…
Figure 6
Figure 6. Figure 6: A choice gadget for V i with |V i | = 3 and the clique vertex c i missing. the set of chosen positions directly gives the desired k-clique in X. We refer to Section 6 for the full details of our construction. As GTE does not allow us to specify possible vertex position…
Figure 7
Figure 7. Figure 7: An instance of Multicolored Clique (bottom), the resulting instance of GTE (with the “tunnels of visibility” marked in gray), and a witness showing we have a positive instance (right). edges as soon as they are required. The subgraph H of G is set to G without the cliq…
Figure 8
Figure 8. Figure 8: A choice gadget with k = 3, |V i | = 3, ϵ = 1 2 , s = 1. The superscript i is dropped for readability. For illustrative purposes, the local blocking edges of al, ad, ar are drawn as well. These edges force the edges from al, ad, ar to the clique vertex to be drawn in r…
Figure 9
Figure 9. Figure 9: Illustration for Lemma 6. the clique vertex c i be drawn in red. Furthermore, around each anchor vertex, we position a red triangle (the left, down, and right triangle) with specific holes in the boundary. Each hole induces a cone where c i can be drawn crossing-free. …
Figure 10
Figure 10. Figure 10: Diagram illustrating how to compute the positions of the barrier vertices of the left triangle. ζ i j/2 |{z} a i d mi j r i d,j α i j ζ i j/2 |{z} mi∗ j ϵ/4} t i d,b,2j−1 t i d,b,2j ϵ/4} [PITH_FULL_IMAGE:figures/full_fig_p022_10.png]
Figure 11
Figure 11. Figure 11: Diagram illustrating how to compute the positions of the barrier vertices of the downward triangle. – The middle points mi 1 , mi 2 , . . . , mi |V i | lie on the x-axis evenly spaced on the interval [−2; 2]. The x-coordinate of the j’th middle point is s ·  4(j − 1)…
Figure 12
Figure 12. Figure 12: Illustration of the various forbidden line segments and a possible placement of a set of global blocking edges. Finally, we set Γs|V (H)\(Bg∪Bl) such that it agrees with the positions we just computed. That is, for all v ∈ V (G) \ {Bg ∪ Bl}, we have Γs(v) := ve. Note …
Figure 12
Figure 12. Figure 12: Elementary trigonometry reveals that their contribution to [PITH_FULL_IMAGE:figures/full_fig_p026_12.png]
Figure 13
Figure 13. Figure 13: An instance of Multicolored Clique (bottom), the resulting instance of GTE, and a witness showing we have a positive instance (right). Note that the position of anchor vertices and the value of ϵ are slightly tweaked to increase readability. and ΓG(x i j ) = mfi j ∈ e…
Figure 14
Figure 14. Figure 14: Example of a positive instance of GTE resulting from our reduction from 3-SAT. The satisfying assignment is x1 7→ 1, x2 7→ 0, x3 7→ 1. Note that the choice gadgets are not fully drawn. that we use the choice gadgets only to constrain these two vertices to two known po…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 23 canonical work pages

  1. [1]

    ACM Trans

    Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. ACM Trans. Algorithms 11(4), 32:1–32:42 (2015).https://doi.org/10.1145/2629341

    doi:10.1145/2629341 2015

  2. [31]

    (eds.): Handbook of discrete and compu- tational geometry

    Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.): Handbook of discrete and compu- tational geometry. Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, third edn. (2018)

    work page 2018

  3. [2]

    In: Beyersdorff, O., Kanté, M.M., Kupferman, O., Lokshtanov, D

    Balabán, J., Ganian, R., Rocton, M.: Computing twin-width parameterized by the feedback edge number. In: Beyersdorff, O., Kanté, M.M., Kupferman, O., Lokshtanov, D. (eds.) 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, 2024, Clermont-Ferrand, France. LIPIcs, vol. 289, pp. 7:1–7:19. Schloss Dagstuhl - Leib...

    doi:10.4230/lipics.stacs.2024.7 2024

  4. [3]

    In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G

    Balko, M., Chaplick, S., Ganian, R., Gupta, S., Hoffmann, M., Valtr, P., Wolff, A.: Bounding and computing obstacle numbers of graphs. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany. LIPIcs, vol. 244, pp. 11:1–11:13. Schloss Dagstuhl - Leib...

    work page doi:10.4230/lipics.esa.2022.11 2022

  5. [4]

    In: Dehne, F., Solis-Oba, R., Sack, J.R

    Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. In: Dehne, F., Solis-Oba, R., Sack, J.R. (eds.) Algorithms and Data Structures. pp. 97–108. Springer Berlin Heidelberg, Berlin, Heidelberg (2013).https://doi.org/ 10.1007/978-3-642-40104-6_9

    work page doi:10.1007/978-3-642-40104-6_9 2013

  6. [5]

    Bannister, M.J., Cabello, S., Eppstein, D.: Parameterized complexity of 1-planarity. J. Graph Algorithms Appl.22(1), 23–49 (2018).https://doi.org/10.7155/JGAA. 00457

    doi:10.7155/jgaa 2018

  7. [6]

    Canadian Journal of Mathematics 17, 850–859 (1965)

    Beineke, L.W., Harary, F.: The thickness of the complete graph. Canadian Journal of Mathematics 17, 850–859 (1965)

    work page 1965

  8. [7]

    In: Chambers, E.W., Gudmundsson, J

    Bhore, S., Ganian, R., Khazaliya, L., Montecchiani, F., Nöllenburg, M.: Extending orthogonal planar graph drawings is fixed-parameter tractable. In: Chambers, E.W., Gudmundsson, J. (eds.) 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA. LIPIcs, vol. 258, pp. 18:1–18:16. Schloss Dagstuhl - Leibniz-Zen...

    doi:10.4230/lipics.socg.2023.18 2023

Show all 43 references
  1. [8]

    Bhore, S., Ganian, R., Montecchiani, F., Nöllenburg, M.: Parameterized algorithms for book embedding problems. J. Graph Algorithms Appl.24(4), 603–620 (2020). https://doi.org/10.7155/JGAA.00526

    2020 doi

  2. [9]

    Bhore, S., Ganian, R., Montecchiani, F., Nöllenburg, M.: Parameterized algorithms for queue layouts. J. Graph Algorithms Appl.26(3), 335–352 (2022).https://doi. org/10.7155/JGAA.00597

    2022 doi

  3. [10]

    Binucci, C., Di Giacomo, E., Lenhart, W.J., Liotta, G., Montecchiani, F., Nöllenburg, M., Symvonis, A.: On the complexity of the storyplan problem. J. Comput. Syst. Sci. 139, 103466 (2024).https://doi.org/10.1016/J.JCSS.2023.103466 34 T. Depian et al

    2024

  4. [11]

    In: Bekos, M.A., Chimani, M

    Brand, C., Ganian, R., Röder, S., Schager, F.: Fixed-parameter algorithms for computing RAC drawings of graphs. In: Bekos, M.A., Chimani, M. (eds.) Graph Drawing and Network Visualization - 31st International Symposium, GD 2023, Isola delle Femmine, Palermo, Italy, September 2...

    2023 doi

  5. [12]

    In: Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers 11

    Brandenburg, F., Eppstein, D., Goodrich, M.T., Kobourov, S., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003 Revised Papers 11. pp. 515–539. Springer (2004)

    2004

  6. [13]

    In: Angelini, P., von Hanxleden, R

    Cheong, O., Pfister, M., Schlipf, L.: The thickness of fan-planar graphs is at most three. In: Angelini, P., von Hanxleden, R. (eds.) Graph Drawing and Network Visualization - 30th International Symposium, GD 2022, Tokyo, Japan, September 13-16, 2022, Revised Selected Papers. ...

    2022 doi

  7. [14]

    Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput.85(1), 12–75 (1990). https://doi.org/10.1016/ 0890-5401(90)90043-H

    1990

  8. [15]

    Springer (2015).https: //doi.org/10.1007/978-3-319-21275-3

    Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015).https: //doi.org/10.1007/978-3-319-21275-3

    2015 doi

  9. [16]

    In: Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

    Depian, T., Fink, S.D., Ganian, R., Nöllenburg, M.: The parameterized complexity of extending stack layouts. In: Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Vienna, Austria (Sep 2024). https://doi.org/10.4230/LIPIcs.GD....

    2024 doi

  10. [17]

    Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173. Springer (2012)

    2012

  11. [18]

    Dillencourt, M.B., Eppstein, D., Hirschberg, D.S.: Geometric thickness of complete graphs. J. Graph Algorithms Appl.4(3), 5–17 (2000).https://doi.org/10.7155/ JGAA.00023

    2000

  12. [19]

    Texts in Computer Science, Springer (2013)

    Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complex- ity. Texts in Computer Science, Springer (2013). https://doi.org/10.1007/ 978-1-4471-5559-1

    2013

  13. [20]

    Dujmović, V., Wood, D.R.: Graph treewidth and geometric thickness parame- ters. Discret. Comput. Geom.37(4), 641–670 (2007).https://doi.org/10.1007/ S00454-007-1318-7

    2007

  14. [21]

    Durocher, S., Gethner, E., Mondal, D.: Thickness and colorability of geometric graphs. Comput. Geom. 56, 1–18 (2016). https://doi.org/10.1016/J.COMGEO. 2016.03.003

    2016 doi

  15. [22]

    Durocher, S., Mondal, D.: Relating graph thickness to planar layers and bend complexity. SIAM J. Discret. Math.32(4), 2703–2719 (2018).https://doi.org/ 10.1137/16M1110042

    2018 doi

  16. [23]

    In: Esparza, J., Král’, D

    Eiben, E., Ganian, R., Hamm, T., Klute, F., Nöllenburg, M.: Extending nearly complete 1-planar drawings in polynomial time. In: Esparza, J., Král’, D. (eds.) 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Cz...

    2020 doi

  17. [24]

    In: Czumaj, A., Dawar, A., Merelli, E

    Eiben, E., Ganian, R., Hamm, T., Klute, F., Nöllenburg, M.: Extending partial 1-planar drawings. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Pathways to Tractability for Geometric Thickness 35 Colloquium on Automata, Languages, and Programming, ICALP 2020,...

    2020

  18. [25]

    In: Kobourov, S.G., Goodrich, M.T

    Eppstein, D.: Separating thickness from geometric thickness. In: Kobourov, S.G., Goodrich, M.T. (eds.) Graph Drawing, 10th International Symposium, GD 2002, Irvine, CA, USA, August 26-28, 2002, Revised Papers. Lecture Notes in Com- puter Science, vol. 2528, pp. 150–161. Spring...

    2002

  19. [26]

    In: Hong, S., Nagamochi, H., Fukunaga, T

    Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Hong, S., Nagamochi, H., Fukunaga, T. (eds.) Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15...

    2008 doi

  20. [27]

    Algorithmica 80(4), 1146–1169 (2018).https://doi.org/10.1007/S00453-017-0297-1

    Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithmica 80(4), 1146–1169 (2018).https://doi.org/10.1007/S00453-017-0297-1

    2018 doi

  21. [28]

    In: Soto, J.A., Wiese, A

    Förster, H., Kindermann, P., Miltzow, T., Parada, I., Terziadis, S., Vogtenhuber, B.: Geometric thickness of multigraphs is∃R-complete. In: Soto, J.A., Wiese, A. (eds.) LATIN 2024: Theoretical Informatics - 16th Latin American Symposium, Puerto Varas, Chile, March 18-22, 2024,...

    2024

  22. [29]

    In: Bansal, N., Merelli, E., Worrell, J

    Ganian, R., Hamm, T., Klute, F., Parada, I., Vogtenhuber, B.: Crossing-optimal extension of simple drawings. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (...

    2021 doi

  23. [30]

    Dagstuhl Reports11(6), 82–123 (2021)

    Ganian, R., Montecchiani, F., Nöllenburg, M., Zehavi, M.: Parameterized complexity in graph drawing (dagstuhl seminar 21293). Dagstuhl Reports11(6), 82–123 (2021). https://doi.org/10.4230/DAGREP.11.6.82

    2021 doi

  24. [32]

    Grigoryev, D.Y., Vorobjov Jr., N.N.: Counting connected components of a semi- algebraic set in subexponential time. Comput. Complex. 2, 133–186 (1992). https://doi.org/10.1007/BF01202001

    1992 doi

  25. [33]

    In: Chambers, E.W., Gudmundsson, J

    Jain, R., Ricci, M., Rollin, J., Schulz, A.: On the geometric thickness of 2-degenerate graphs. In: Chambers, E.W., Gudmundsson, J. (eds.) 39th International Symposium on Computational Geometry, SoCG 2023, June 12-15, 2023, Dallas, Texas, USA. LIPIcs, vol. 258, pp. 44:1–44:15....

    2023 doi

  26. [34]

    In: Mathematical Proceedings of the Cambridge Philosophical Society

    Mansfield, A.: Determining the thickness of graphs is np-hard. In: Mathematical Proceedings of the Cambridge Philosophical Society. vol. 93, pp. 9–23. Cambridge University Press (1983)

    1983

  27. [35]

    Graphs Comb

    Mutzel, P., Odenthal, T., Scharbrodt, M.: The thickness of graphs: A survey. Graphs Comb. 14(1), 59–73 (1998).https://doi.org/10.1007/PL00007219

    1998 doi

  28. [36]

    Algorithms and Combinatorics28, xxiv+– 457 (2012)

    Nešetřil, J., de Mendez, P.O.: Sparsity. Algorithms and Combinatorics28, xxiv+– 457 (2012). https://doi.org/10.1007/978-3-642-27875-4 36 T. Depian et al

    2012 doi

  29. [37]

    Nesetril, J., de Mendez, P.O.: Sparsity - Graphs, Structures, and Algorithms, Algorithms and combinatorics, vol. 28. Springer (2012).https://doi.org/10.1007/ 978-3-642-27875-4

    2012

  30. [38]

    Robertson, N., Seymour, P.D.: Graph minors. i. excluding a forest. J. Comb. Theory, Ser. B 35(1), 39–61 (1983).https://doi.org/10.1016/0095-8956(83)90079-5

    1983 doi

  31. [39]

    Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986). https://doi.org/10.1016/0196-6774(86) 90023-4

    1986 doi

  32. [40]

    In: Eppstein, D., Gansner, E.R

    Schaefer, M.: Complexity of some geometric and topological problems. In: Eppstein, D., Gansner, E.R. (eds.) Graph Drawing (GD’09). LNCS, vol. 5849, pp. 334–344. Springer (2009). https://doi.org/10.1007/978-3-642-11805-0_32

    2009 doi

  33. [41]

    CRC press (2017)

    Toth, C.D., O’Rourke, J., Goodman, J.E.: Handbook of discrete and computational geometry. CRC press (2017)

    2017

  34. [42]

    Tutte, W.T.: The thickness of a graph. Indag. Math.25, 561–577 (1963)

    1963

  35. [43]

    Zehavi, M.: Parameterized analysis and crossing minimization problems. Comput. Sci. Rev. 45, 100490 (2022).https://doi.org/10.1016/J.COSREV.2022.100490

    2022

Pith tools

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