Pith. sign in

REVIEW 6 minor 66 references

Given an outer k-planar drawing, many treewidth-hard problems become FPT in the crossing bound k; only a few stay XALP-complete.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-30 16:29 UTC pith:TAZOB7HP

load-bearing objection Solid landscape paper: given an outer k-planar drawing, most of the XALP-by-treewidth catalogue becomes FPT via one geometric invariant; a few stay hard; hierarchy placement is clean.

arxiv 2607.26936 v1 pith:TAZOB7HP submitted 2026-07-29 cs.DS cs.CCcs.CG

The Parameterized Complexity of Problems on Outer k-Planar Graphs

Xiaobin Ren , Hans L. Bodlaender This is my paper
classification cs.DS cs.CCcs.CG MSC 68Q2768R1005C1005C85
keywords outer k-planar graphsparameterized complexityXALP-completenessfixed-parameter tractabilitymim-widthcut-widthtriangulationdynamic programming
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Outer k-planar graphs place every vertex on a circle and allow each edge at most k crossings. Many classical problems are XALP-complete when parameterized by treewidth or outerplanarity. This paper shows that, once an outer k-planar drawing is supplied, a large family of those problems—including List Coloring, capacitated domination and vertex cover, several orientation and flow problems, f- and q-domination, and Target Set Selection—become fixed-parameter tractable in k. Binary CSP and Scattered Set remain XALP-complete even on this class. The algorithms rest on a triangulation of the outer cycle in which each added chord crosses the original drawing at most k times; the weak dual of that triangulation supplies a tree-shaped dynamic-programming skeleton whose boundary interactions are tightly controlled by the geometry. Structural side results place outer k-planarity in the parameter hierarchy: mim-width is at most k+2, cut-width k implies outer 2k-planarity, and feedback edge set k implies outer 6k-planarity, while many other parameters are incomparable with it.

Core claim

Assuming an outer k-planar drawing is given, most of the problems that are XALP-complete parameterized by treewidth or outerplanarity become FPT parameterized by k, while Binary CSP and Scattered Set stay XALP-complete on outer k-planar graphs parameterized by k. The same geometric structure also yields mim-width ≤ k+2 and shows that bounded cut-width or feedback edge set number implies bounded outer planarity.

What carries the argument

The Firman–et–al. triangulation of the outer cycle: every triangulation link crosses the original drawing at most k times. Its weak dual is a binary tree that organizes bottom-up dynamic programming; each link yields a separator of size ≤ k+2 whose non-endpoint boundary vertices have at most k exterior neighbors, turning many XP treewidth tables into FPT tables (sometimes after representative-set compression).

Load-bearing premise

Every FPT algorithm is given not only the graph and k but an outer k-planar drawing (and the associated triangulation); without the drawing the tractability claims do not apply, and recognition itself is already hard.

What would settle it

Exhibit a concrete problem from the “FPT” list that remains W[1]- or XALP-hard on outer k-planar graphs even when a drawing is provided, or produce a polynomial algorithm that builds an outer f(k)-planar drawing from any graph of treewidth k, collapsing the drawing assumption.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • List Coloring, Precoloring Extension, Capacitated Dominating Set, Capacitated Vertex Cover, Target Outdegree Orientation, All-or-Nothing Flow, Circulating Orientation, f-/q-Dominating Set and Target Set Selection are all FPT on outer k-planar graphs once a drawing is known.
  • Binary CSP and Scattered Set remain XALP-complete parameterized by outer k-planarity, so the geometric restriction does not tame every treewidth-hard problem.
  • Outer k-planar graphs have mim-width at most k+2, giving a new structural upper bound tighter than the one inherited from treewidth.
  • Every graph of cut-width ≤ k (hence bandwidth ≤ k) admits an outer 2k-planar (resp. outer 2k²-planar) drawing; every graph of feedback edge set number ≤ k admits an outer 6k-planar drawing.
  • Outer k-planarity sits strictly between several classical width measures in the parameter hierarchy and is incomparable with pathwidth, feedback vertex set, tree-cut width and many others.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because recognition is XNLP-hard, practical use of the FPT results will require either drawings supplied by the application or approximation/heuristic construction of low-crossing circular layouts.
  • The same triangulation-plus-bounded-exterior-degree pattern is likely to convert other XP algorithms on tree decompositions into FPT algorithms whenever the natural state per bag vertex is polynomial only in the number of exterior neighbors.
  • Problems whose hardness gadgets force large K_{2,m} minors or similar high-crossing bipartite configurations are precisely those expected to stay hard; problems whose constraints are local to small separators are the ones that drop to FPT.
  • Combining the mim-width bound with existing mim-width algorithms may yield alternative FPT routes for some of the same problems without explicitly building the triangulation DP.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 6 minor

Summary. The paper studies the parameterized complexity of many classical graph problems on outer k-planar graphs (parameter k = convex local crossing number), assuming an outer k-planar drawing is given. It shows that Binary CSP and Scattered Set remain XALP-complete parameterized by k, while a large class of problems that are XALP-complete by treewidth/outerplanarity—including List Coloring, Precoloring Extension, Capacitated (Red-Blue) Dominating Set, Capacitated Vertex Cover, several outdegree-orientation and flow problems, f-/q-Dominating Set, and Target Set Selection—become FPT via dynamic programming on the Firman et al. triangulation of the outer cycle. Structurally, it proves mim-width ≤ k+2, that cut-width ≤ k implies outer 2k-planarity (hence bandwidth ≤ k implies outer 2k²-planarity), that feedback edge set number ≤ k implies outer 6k-planarity, and that outer k-planarity is incomparable with many standard parameters, clarifying its place in the hierarchy.

Significance. The work cleanly separates problems whose hardness survives the geometric restriction of outer k-planarity from those that become FPT once the drawing (and triangulation) is available. The reusable geometric invariant—each triangulation link crossed by at most k edges, so only two link endpoints need n-sized residuals while interface vertices are O(k)—unifies a long list of FPT algorithms and is a useful template beyond the problems treated here. The structural results (mim-width, cut-width/bandwidth and feedback-edge-set implications, incomparability table) usefully locate outer k-planarity in the parameter hierarchy. The drawing-given caveat is stated up front and matches the known XNLP-hardness of recognition; the theorems are correctly scoped. Overall this is a solid, broad contribution to beyond-planar parameterized algorithms.

minor comments (6)
  1. [Table 1 / Abstract] Abstract and §1.1 correctly flag that FPT algorithms assume a given outer k-planar drawing; it would help readers if Table 1’s caption or a footnote also stated this assumption explicitly next to the FPT entries.
  2. [§4.1] In §4.1 the crossing bound for the Binary CSP gadget is argued as O(k); stating an explicit constant (e.g., ≤5k+5 as in the text) in the theorem statement or proof summary would make the parameter blow-up fully transparent.
  3. [§5] Several DP sections (§§5.2–5.6) reuse the same separator/boundary notation (Pt, At, Bt, dout_t). A short common “DP setup” subsection before 5.1, with a single figure of the merge, would reduce repetition and ease verification of the merge rules.
  4. [§5.4] Theorem 7 and Corollaries 3–4 assume unary encoding of weights/targets; this is stated in the theorems but could be echoed once in the introduction of §5.4 for readers skimming.
  5. [§6 / Figure 18] Figure 18 (parameter hierarchy) is referenced in §1.1 and §6 but the excerpt ends mid-proof of Theorem 13; ensure the final figure and the distance-to-outerplanar argument in §6.3 are complete and consistently labeled in the camera-ready version.
  6. [§1, global] Minor typos/style: “this thesis” in §1 should be “this paper”; occasional missing spaces before citations; standardize lcr°(G) vs outer k-planarity in table headers.

Circularity Check

0 steps flagged

No significant circularity: FPT/hardness claims are independent DPs and reductions on an external geometric lemma

full rationale

The paper’s load-bearing chain is: (i) take an outer k-planar drawing as input; (ii) apply Firman et al.’s triangulation (Lemma 1, external) so each link is crossed ≤k times; (iii) run new bottom-up DPs on the weak dual, or new XALP-hardness reductions that embed generalized tree decompositions into outer O(k)-planar drawings. Prior XALP/XNLP completeness for treewidth/pathwidth/outerplanarity (including Bodlaender coauthored work) is used only as the comparison baseline in Table 1, not as a substitute for the new proofs. Mim-width ≤k+2, cut-width⇒outer 2k-planar, and feedback-edge-set⇒outer 6k-planar are self-contained combinatorial arguments. There are no fitted parameters, no ‘predictions’ forced by construction, no uniqueness theorems imported from the authors, and no renaming of a known empirical pattern. The drawing-given caveat is disclosed, not hidden. Score 0 is appropriate.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 1 invented entities

Load-bearing background is standard parameterized complexity plus one external geometric lemma (outer-cycle triangulation with ≤k crossings per link) and the modeling choice that drawings are given. No empirical free parameters. Invented objects are definitional (outer k-planar, convex local crossing number) rather than speculative physical entities.

axioms (5)
  • domain assumption Firman et al. Lemma 6: given an outer k-planar drawing, the outer cycle admits a triangulation in which each triangulation edge crosses the original graph at most k times, constructible in O(nk) time from the edge intersection graph.
    Invoked as Lemma 1; every FPT DP and the mim-width proof route through this triangulation and its weak dual tree.
  • domain assumption Outer k-planar graphs have treewidth at most 1.5k+2 (Firman et al.), hence XALP membership for problems already in XALP by treewidth follows for parameter k.
    Used for membership side of XALP-completeness in §4.
  • standard math Standard definitions and closure properties of XNLP/XALP under pl/ptl-reductions; SPSC mentioned only as context.
    §2.1; hardness proofs omit some logspace bookkeeping as ‘standard.’
  • ad hoc to paper Input includes an outer k-planar drawing (recognition is XNLP-hard by Kobayashi et al.).
    Stated in abstract and §1; without it FPT claims are not algorithmic end-to-end from abstract graphs.
  • domain assumption For orientation/flow FPT results, edge weights and targets are encoded in unary where stated.
    Theorems 7–9 and corollaries; needed so residual tables stay FPT-size.
invented entities (1)
  • Convex local crossing number lcr°(G) as the parameter (outer k-planarity) independent evidence
    purpose: Name the minimization parameter equal to the smallest k such that G is outer k-planar; organize Table 1 and hierarchy comparisons.
    Standard beyond-planar terminology cited from the literature; not a new physical object.

pith-pipeline@v1.2.0-daily-grok45 · 60372 in / 3153 out tokens · 71528 ms · 2026-07-30T16:29:29.945529+00:00 · methodology

0 comments
read the original abstract

A graph is outer k-planar if it admits a straight-line drawing in which all vertices lie on a circle and every edge is crossed by at most k other edges. We study the parameterized complexity of a broad collection of graph problems on outer k-planar graphs, with k as the parameter. Many graph problems are known to be XALP-hard when parameterized by treewidth or outerplanarity, and XNLP-hard when parameterized by pathwidth. We show that only a few such problems, including Binary CSP and Scattered Set, remain intractable on outer k-planar graphs, whereas a large class of the others become fixed-parameter tractable in this setting, assuming that an outer k-planar drawing of the input graph is given. These include List Coloring, Capacitated Dominating Set, Capacitated Vertex Cover, Target Outdegree Orientation, and Target Set Selection, among others. In addition to the algorithmic and complexity results, we establish several structural results. We show that outer k-planar graphs have mim-width at most k+2, that graphs of cut-width at most k are outer 2k-planar, and that graphs of feedback edge set number at most k are outer 6k-planar. We also show that many graph parameters are incomparable with outer k-planarity, thereby clarifying its position within the graph parameter hierarchy.

Figures

Figures reproduced from arXiv: 2607.26936 by Hans L. Bodlaender, Xiaobin Ren.

Figure 1
Figure 1. Figure 1: After triangulating the outer cycle, the weak dual of this triangulation is a tree, [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An example illustrating the bottom-up construction of the subcubic tree [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: uX vX wX xX vY wY xY uY uX vX vY wX wY xX xY uX uY vX vY wX wY xX xY uX vX uY vY wX wY xX xY uX vX wX uY vY wY uZ vZ wZ [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An example of edges incident with the vertices of a join bag [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Suppose that the shortest path from u to v in G is u → x → y → v. In H, all copies of each vertex i ∈ V (G) form a connected subtree Ti . Different subtrees are connected by long path gadgets. There exists a path from Ru to Rv in H that traverses the long path gadgets corresponding to the Add-Edge bags for the edges ux, xy, and yv. Each subtree Ti can be viewed as a super-vertex, represented by a pink circ… view at source ↗
Figure 6
Figure 6. Figure 6: In an Add-Edge bag X, the vertices vX and wX are connected by a long path gadget (marked in red). All non-representative vertices and the vertices on the long path gadget are each attached to two pendant paths (marked in blue). The figure on the right illustrates how these pendant paths can be drawn on the outer face without introducing additional crossings. a d ′ -scattered set of size m′ in H, and vice v… view at source ↗
Figure 7
Figure 7. Figure 7: The triangulation link λt = atbt separates the convex polygon into two subpoly￾gons. The lower subpolygon consists of a collection of triangles whose corresponding nodes in the weak dual form a rooted subtree of the weak dual. Vertices in such a subpolygon can represent a subproblem in the dynamic programming. Subpolygons Pt1 and Pt2 denote the two subproblems induced by the links atct and btct , respectiv… view at source ↗
Figure 8
Figure 8. Figure 8: For the subpolygon (or equivalently, subproblem) [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The endpoints of all edges crossing the triangulation link [PITH_FULL_IMAGE:figures/full_fig_p021_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Each triangulation link λt = atbt separates the triangulated graph into two subpolygons. Let Pt1 and Pt2 denote the two subproblems induced by the links atc and btc, respectively. The boundary vertices of subpolygon Pt1 are Bt1 = {at , x1, c}, and At1 = {x1}, while the boundary vertices of Pt2 are Bt2 = {bt , x2, c}, and At2 = {x2}. The boundary vertices of subpolygon Pt (obtained by merging the three col… view at source ↗
Figure 11
Figure 11. Figure 11: An example of merging internal nodes t1 and t2 to compute the DP table for node t. Vertices in Bt1 on the outer cycle are marked in red, vertices in Bt2 are marked in blue, and the vertex c shared by the two subproblems is marked in green. The figure on the left shows the merging of t1 and t2, while the right one shows node t after the merge, used for the next step of further merging. Some triangulation l… view at source ↗
Figure 12
Figure 12. Figure 12: An illustration of how to handle an internal node with only one child problem. [PITH_FULL_IMAGE:figures/full_fig_p030_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: The standard activation order a, b,(c, d, e), f induced by repeatedly propa￾gating activations from S = {a} is not the only valid activation order. Another order, a, b,(d, e), f, c, is also valid. Moreover, the latter can be reordered so that each vertex appears at its earliest possible activation time, thereby recovering the former sequence. Both orders certify that the seed set S = {a} is a feasible sol… view at source ↗
Figure 14
Figure 14. Figure 14: A sequence of triangles can be embedded as an outerplanar graph, which [PITH_FULL_IMAGE:figures/full_fig_p057_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: An example illustrating how three skeleton edges in [PITH_FULL_IMAGE:figures/full_fig_p060_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Every tree attached to a vertex a ∈ V (C) can have its vertices placed consecutively in an interval of the outer face adjacent to a according to a pre-order traversal. The edges of these trees do not cross any other edges of the graph. Hence, after reconstructing G from the 2-core graph C, every edge still has at most 6r − 7 crossings. It remains to insert the trees that were deleted when passing from G t… view at source ↗
Figure 17
Figure 17. Figure 17: A sequence of connected disjoint copies of [PITH_FULL_IMAGE:figures/full_fig_p061_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: The position of outer k-planarity within the graph parameter hierarchy, as implied by the currently known boundedness and unboundedness results. An arc from parameter a to parameter b indicates that bounded a implies bounded b. Only a selection of commonly studied and related parameters, as well as their relationships are shown. 62 [PITH_FULL_IMAGE:figures/full_fig_p062_18.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

66 extracted references · 31 canonical work pages · 2 internal anchors

  1. [1]

    Eliminating crossings in ordered graphs

    Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. Eliminating crossings in ordered graphs. In19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:19. Schloss Dagstuhl – Leibniz-Zentrum f...

    doi:10.4230/lipics.swat.2024.1 2024

  2. [2]

    Edge partitions of complete geometric graphs

    Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber, Rosna Paul, Patrick Schnider, Raphael Steiner, Tim Taubner, and Birgit Vogtenhuber. Edge partitions of complete geometric graphs. In38th International Symposium on Computational Ge- ometry (SoCG 2022), volume 224 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:16. Schloss Dagst...

    doi:10.4230/lipics.socg.2022.6 2022

  3. [3]

    Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber

    Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber. Outer 1-planar graphs. Algorithmica, 74(4):1293–1320, 2016.doi:10.1007/s00453-015-0002-1

    work page doi:10.1007/s00453-015-0002-1 2016

  4. [4]

    Parameterized complexity of 1-planarity.Journal of Graph Algorithms and Applications, 22:23–49, 2018.doi: 10.7155/jgaa.00457

    Michael Bannister, Sergio Cabello, and David Eppstein. Parameterized complexity of 1-planarity.Journal of Graph Algorithms and Applications, 22:23–49, 2018.doi: 10.7155/jgaa.00457

    work page doi:10.7155/jgaa.00457 2018

  5. [5]

    Treewidth governs the complexity of target set selection.Discrete Optimization, 8(1):87–96, 2011.doi:10.1016/j.disopt.2010.09.007

    Oren Ben-Zwi, Danny Hermelin, Daniel Lokshtanov, and Ilan Newman. Treewidth governs the complexity of target set selection.Discrete Optimization, 8(1):87–96, 2011.doi:10.1016/j.disopt.2010.09.007. 64

    doi:10.1016/j.disopt.2010.09.007 2011

  6. [6]

    Min-k-planar drawings of graphs.Journal of Graph Algorithms and Applications, 28(2):1–35, 2024.doi:10.7155/jgaa.v28i2.2925

    Carla Binucci, Aaron Büngener, Giuseppe Di Battista, Walter Didimo, Vida Dujmović, Seok-Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tap- pini. Min-k-planar drawings of graphs.Journal of Graph Algorithms and Applications, 28(2):1–35, 2024.doi:10.7155/jgaa.v28i2.2925

    doi:10.7155/jgaa.v28i2.2925 2024

  7. [7]

    Bodlaender

    Hans L. Bodlaender. A partialk-arboretum of graphs with bounded treewidth.The- oretical Computer Science, 209(1):1–45, 1998.doi:10.1016/S0304-3975(97) 00228-4

    work page doi:10.1016/s0304-3975(97 1998

  8. [8]

    Bodlaender, Gunther Cornelissen, and Marieke van der Wegen

    Hans L. Bodlaender, Gunther Cornelissen, and Marieke van der Wegen. Problems hard for treewidth but easy for stable gonality. In48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), volume 13453 of Lecture Notes in Computer Science, pages 84–97. Springer, 2022.doi:10.1007/ 978-3-031-15914-5_7

    2022

  9. [9]

    Bodlaender, Carla Groenland, and Hugo Jacob

    Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. List colouring trees in logarithmic space. In30th Annual European Symposium on Algorithms (ESA 2022), volume 244 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 24:1– 24:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.doi:10.4230/ LIPIcs.ESA.2022.24

    2022

  10. [10]

    Bodlaender, Carla Groenland, and Hugo Jacob

    Hans L. Bodlaender, Carla Groenland, and Hugo Jacob. On the parameterized com- plexity of computing tree-partitions.Discrete Mathematics & Theoretical Computer Science, vol. 26:3, 2025.doi:10.46298/dmtcs.12540

    work page doi:10.46298/dmtcs.12540 2025

  11. [11]

    Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T

    Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T. Lima. XNLP-completeness for parameterized problems on graphs with a linear structure. Algorithmica, 87(4):465–506, 2025.doi:10.1007/S00453-024-01274-9

    work page doi:10.1007/s00453-024-01274-9 2025

  12. [12]

    Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk

    Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk. On the complexity of problems on tree-structured graphs. In17th International Symposium on Parameterized and Exact Computation (IPEC 2022), volume 249 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 6:1– 6:17. Schloss Dagstuhl – Leibniz-Zentrum für ...

    2022

  13. [13]

    Bodlaender, Carla Groenland, Jesper Nederlof, and Céline M

    Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, and Céline M. F. Swennenhuis. Parameterized problems complete for nondeterministic FPT time and logarithmic space.Information and Compututation, 300:105195, 2024. doi:10.1016/J.IC. 2024.105195

    arXiv 2024

  14. [14]

    Bodlaender, Daniel Lokshtanov, and Eelko Penninkx

    Hans L. Bodlaender, Daniel Lokshtanov, and Eelko Penninkx. Planar capacitated dominating set is W[1]-hard. In Jianer Chen and Fedor V. Fomin, editors,Parameter- ized and Exact Computation, pages 50–60, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.doi:10.1007/978-3-642-11269-0_4

    work page doi:10.1007/978-3-642-11269-0_4 2009

  15. [15]

    Bodlaender and Krisztina Szilágyi

    Hans L. Bodlaender and Krisztina Szilágyi. XALP-completeness of parameterized problems on planar graphs.Discrete Applied Mathematics, 386:156–174, 2026.doi: 10.1016/j.dam.2026.01.021. 65

    work page doi:10.1016/j.dam.2026.01.021 2026

  16. [16]

    Stretch-width

    Édouard Bonnet and Julien Duron. Stretch-width. In18th International Symposium on Parameterized and Exact Computation (IPEC 2023), volume 285 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.doi:10.4230/LIPIcs.IPEC.2023.8

    work page doi:10.4230/lipics.ipec.2023.8 2023

  17. [17]

    Edge-cut width: An algorithmically driven analogue of treewidth based on edge cuts

    Cornelius Brand, Esra Ceylan, Robert Ganian, Christian Hatschka, and Viktoriia Korchemna. Edge-cut width: An algorithmically driven analogue of treewidth based on edge cuts. In48th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2022), volume 13453 ofLecture Notes in Computer Science, pages 98–113. Springer, 2022.doi:10.1007/978...

    work page doi:10.1007/978-3-031-15914-5_8 2022

  18. [18]

    Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and David R

    Rutger Campbell, Katie Clinch, Marc Distel, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and David R. Wood. Product structure of graph classes with bounded treewidth. Combinatorics, Probability and Computing, 33(3):351–376, 2024.doi:10.1017/ S0963548323000457

    2024

  19. [19]

    A new width parameter of graphs based on edge cuts:α-edge-crossing width.Discrete Applied Mathematics, 380:492–510, 2026.doi:10.1016/j.dam.2025.10.056

    Yeonsu Chang, O-joung Kwon, and Myounghwan Lee. A new width parameter of graphs based on edge cuts:α-edge-crossing width.Discrete Applied Mathematics, 380:492–510, 2026.doi:10.1016/j.dam.2025.10.056

    work page doi:10.1016/j.dam.2025.10.056 2026

  20. [20]

    Beyond outerplanarity

    Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre Löffler, and Alexander Wolff. Beyond outerplanarity. In25th International Symposium on Graph Drawing and Network Visualization (GD 2018), volume10692ofLecture Notes in Computer Science, pages 546–559. Springer, 2018.doi:10.1007/978-3-319-73915-1_42

    doi:10.1007/978-3-319-73915-1_42 2018

  21. [21]

    Upper bounds forf-domination number of graphs

    Beifang Chen and Sanming Zhou. Upper bounds forf-domination number of graphs. Discrete Mathematics, 185(1):239–243, 1998. doi:10.1016/S0012-365X(97) 00204-5

    work page doi:10.1016/s0012-365x(97 1998

  22. [22]

    Fan R. K. Chung. On the cutwidth and the topological bandwidth of a tree. SIAM Journal on Algebraic Discrete Methods, 6(2):268–277, 1985.doi:10.1137/ 0606026

    1985

  23. [23]

    Corneil and Udi Rotics

    Derek G. Corneil and Udi Rotics. On the relationship between clique-width and treewidth.SIAM Journal on Computing, 34(4):825–847, 2005. doi:10.1137/ S0097539701385351

    2005

  24. [24]

    On quasi-planar graphs: Clique-width and logical description

    Bruno Courcelle. On quasi-planar graphs: Clique-width and logical description. Discrete Applied Mathematics, 278:118–135, 2020.doi:10.1016/j.dam.2018. 07.022

    work page doi:10.1016/j.dam.2018 2020

  25. [25]

    Upper bounds to the clique width of graphs.Dis- crete Applied Mathematics, 101(1):77–114, 2000.doi:10.1016/S0166-218X(99) 00184-5

    Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs.Dis- crete Applied Mathematics, 101(1):77–114, 2000.doi:10.1016/S0166-218X(99) 00184-5

    work page doi:10.1016/s0166-218x(99 2000

  26. [26]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015.doi:10.1007/978-3-319-21275-3

    doi:10.1007/978-3-319-21275-3 2015

  27. [27]

    A survey on graph drawing beyond planarity.ACM Computing Surveys, 52(1), 2019.doi:10.1145/ 3301281

    Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity.ACM Computing Surveys, 52(1), 2019.doi:10.1145/ 3301281. 66

    2019

  28. [28]

    HV-planarity: Algorithms and complexity.Journal of Computer and System Sciences, 99:72–90, 2019.doi: 10.1016/j.jcss.2018.08.003

    Walter Didimo, Giuseppe Liotta, and Maurizio Patrignani. HV-planarity: Algorithms and complexity.Journal of Computer and System Sciences, 99:72–90, 2019.doi: 10.1016/j.jcss.2018.08.003

    work page doi:10.1016/j.jcss.2018.08.003 2019

  29. [29]

    Marc Distel and David R. Wood. Tree-partitions with bounded degree trees. In 2021-2022 MATRIX Annals, volume 5 ofMATRIX Book Series, pages 203–212. Springer, 2024.doi:10.1007/978-3-031-47417-0_11

    work page doi:10.1007/978-3-031-47417-0_11 2021

  30. [30]

    Capac- itated domination and covering: A parameterized perspective

    Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Capac- itated domination and covering: A parameterized perspective. In3rd Interna- tional Workshop on Parameterized and Exact Computation (IWPEC 2008), vol- ume 5018 ofLecture Notes in Computer Science, pages 78–90. Springer, 2008. doi:10.1007/978-3-540-79723-4_9

    work page doi:10.1007/978-3-540-79723-4_9 2008

  31. [31]

    Downey and Michael R

    Rod G. Downey and Michael R. Fellows. Fixed-parameter tractability and complete- ness II: On completeness for W[1].Theoretical Computer Science, 141(1):109–131, 1995.doi:10.1016/0304-3975(94)00097-3

    doi:10.1016/0304-3975(94)00097-3 1995

  32. [32]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows.Parameterized Complexity. Monographs in Computer Science. Springer, 1999.doi:10.1007/978-1-4612-0515-9

    doi:10.1007/978-1-4612-0515-9 1999

  33. [33]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows.Fundamentals of Parameter- ized Complexity. Texts in Computer Science. Springer, 2013. doi:10.1007/ 978-1-4471-5559-1

    2013

  34. [34]

    Beyond-Planar Graphs: Models, Structures and Geometric Representations (Dagstuhl Seminar 24062).Dagstuhl Reports, 14(2):71–94, 2024

    Vida Dujmović, Seok-Hee Hong, Michael Kaufmann, János Pach, and Henry Förster. Beyond-Planar Graphs: Models, Structures and Geometric Representations (Dagstuhl Seminar 24062).Dagstuhl Reports, 14(2):71–94, 2024. doi:10.4230/DagRep.14. 2.71

    work page doi:10.4230/dagrep.14 2024

  35. [35]

    Distance-d independent set problems for bipartite and chordal graphs.Journal of Combinatorial Optimization, 27(1):88–99, 2014.doi:10.1007/s10878-012-9594-4

    Hiroshi Eto, Fengrui Guo, and Eiji Miyano. Distance-d independent set problems for bipartite and chordal graphs.Journal of Combinatorial Optimization, 27(1):88–99, 2014.doi:10.1007/s10878-012-9594-4

    doi:10.1007/s10878-012-9594-4 2014

  36. [36]

    Fellows, Fedor V

    Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth.Information and Computation, 209(2):143–153, 2011.doi:10.1016/j.ic.2010.11.026

    doi:10.1016/j.ic.2010.11.026 2011

  37. [37]

    J. F. Fink and M. S. Jacobson.n-Domination in graphs. InGraph Theory with Applications to Algorithms and Computer Science, page 283–300. John Wiley & Sons,

  38. [38]

    Bounding the treewidth of outer k-planar graphs via triangulations

    Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff. Bounding the treewidth of outer k-planar graphs via triangulations. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024), volume 320 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:17. Schloss Dagstuhl – Leibniz-Ze...

    work page doi:10.4230/lipics.gd.2024.14 2024

  39. [39]

    Texts in The- oretical Computer Science

    Jörg Flum and Martin Grohe.Parameterized Complexity Theory. Texts in The- oretical Computer Science. An EATCS Series. Springer, 2006. doi:10.1007/ 3-540-29953-X. 67

    2006

  40. [40]

    Fomin, Petr A

    Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique-width.SIAM Journal on Computing, 43(5):1541–1563, 2014.doi:10.1137/130910932

    work page doi:10.1137/130910932 2014

  41. [41]

    Bodlaender

    Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge.Algorithmica, 49(1):1–11, 2007. doi:10.1007/ s00453-007-0010-x

    2007

  42. [42]

    R. Halin. Tree-partitions of infinite graphs.Discrete Mathematics, 97(1):203–217, 1991.doi:10.1016/0012-365X(91)90436-6

    work page doi:10.1016/0012-365x(91)90436-6 1991

  43. [43]

    On a tree-based variant of bandwidth and forbidding simple topological minors

    Hugo Jacob, William Lochet, and Christophe Paul. On a tree-based variant of bandwidth and forbidding simple topological minors.arXiv, (2502.11674), 2025. doi:10.48550/arXiv.2502.11674

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2502.11674 2025

  44. [44]

    A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width

    Lars Jaffke, O-joung Kwon, and Jan Arne Telle. A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width. In35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume 96 ofLeibniz International Proceedings in Informatics (LIPIcs), pages42:1–42:14.SchlossDagstuhl– Leibniz-Zentrum für Informatik, 2018.doi...

    work page doi:10.4230/lipics.stacs.2018.42 2018

  45. [45]

    Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, and Kirill Simonov. Upward and rectilinear planarity are W[1]-hard parameterized by treewidth.SIAM Journal on Discrete Mathematics, 40(2):706–742, 2026.doi:10.1137/24M1679240

    work page doi:10.1137/24m1679240 2026

  46. [46]

    Generalized coloring for tree-like graphs.Dis- crete Applied Mathematics, 75(2):135–155, 1997.doi:10.1016/S0166-218X(96) 00085-6

    Klaus Jansen and Petra Scheffler. Generalized coloring for tree-like graphs.Dis- crete Applied Mathematics, 75(2):135–155, 1997.doi:10.1016/S0166-218X(96) 00085-6

    work page doi:10.1016/s0166-218x(96 1997

  47. [47]

    Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally pa- rameterized d-scattered set.Discrete Applied Mathematics, 308:168–186, 2022. doi:10.1016/j.dam.2020.03.052

    doi:10.1016/j.dam.2020.03.052 2022

  48. [48]

    Springer, 1994.doi:10.1007/BFb0045375

    Ton Kloks.Treewidth, Computations and Approximations, volume 842 ofLecture Notes in Computer Science. Springer, 1994.doi:10.1007/BFb0045375

    work page doi:10.1007/bfb0045375 1994

  49. [49]

    Recognizing 2-layer and outer k-planar graphs

    Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff. Recognizing 2-layer and outer k-planar graphs. In41st International Symposium on Computational Geometry (SoCG 2025), volume 332 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 65:1–65:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.doi: 10.4230/LIPIcs.SoCG.2025.65

    work page doi:10.4230/lipics.socg.2025.65 2025

  50. [50]

    Parameterized Capacitated Vertex Cover Revisited

    Michael Lampis and Manolis Vasilakis. Parameterized capacitated vertex cover revisited.arXiv, (2604.18746), 2026.doi:10.48550/arXiv.2604.18746

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2604.18746 2026

  51. [51]

    Algorithms and Combinatorics, 28

    Jaroslav Nešetřil.Sparsity : Graphs, Structures, and Algorithms. Algorithms and Combinatorics, 28. Springer, 2012.doi:10.1007/978-3-642-27875-4

    doi:10.1007/978-3-642-27875-4 2012

  52. [52]

    Graphs drawn with few crossings per edge.Combinatorica, 17(3):427–439, 1997.doi:10.1007/BF01215922

    János Pach and Géza Tóth. Graphs drawn with few crossings per edge.Combinatorica, 17(3):427–439, 1997.doi:10.1007/BF01215922. 68

    doi:10.1007/bf01215922 1997

  53. [53]

    On space efficiency of algorithms working on structural decompositions of graphs.ACM Transactions on Computation Theory, 9(4), 2018.doi:10.1145/3154856

    Michał Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs.ACM Transactions on Computation Theory, 9(4), 2018.doi:10.1145/3154856

    doi:10.1145/3154856 2018

  54. [54]

    Treewidth of outerk-planar graphs

    Rafał Pyzik. Treewidth of outerk-planar graphs. In33rd International Symposium on Graph Drawing and Network Visualization (GD 2025), volume 357 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.doi:10.4230/LIPIcs.GD.2025.28

    work page doi:10.4230/lipics.gd.2025.28 2025

  55. [55]

    Ein Sechsfarbenproblem auf der Kugel.Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 29(1):107–117, 1965.doi:10

    Gerhard Ringel. Ein Sechsfarbenproblem auf der Kugel.Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 29(1):107–117, 1965.doi:10. 1007/BF02996313

    1965

  56. [56]

    James B. Saxe. Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time.SIAM Journal on Algebraic Discrete Methods, 1(4):363– 369, 1980.doi:10.1137/0601042

    doi:10.1137/0601042 1980

  57. [57]

    The graph crossing number and its variants: A survey.Electronic Journal of Combinatorics, (DS21), 2013.doi:10.37236/2713

    Marcus Schaefer. The graph crossing number and its variants: A survey.Electronic Journal of Combinatorics, (DS21), 2013.doi:10.37236/2713

    doi:10.37236/2713 2013

  58. [58]

    D. Seese. Tree-partite graphs and the complexity of algorithms. In5th International Symposium on Fundamentals of Computation Theory (FCT 1985), volume 199 of Lecture Notes in Computer Science, pages 412–421. Springer, 1985.doi:10.1007/ BFb0028825

    1985

  59. [59]

    Bandwidth of the completek-ary tree.Discrete Mathematics, 142(1–3):203–212, 1995.doi:10.1016/0012-365X(93)E0219-T

    Lawren Smithline. Bandwidth of the completek-ary tree.Discrete Mathematics, 142(1–3):203–212, 1995.doi:10.1016/0012-365X(93)E0219-T

    work page doi:10.1016/0012-365x(93)e0219-t 1995

  60. [60]

    Complexity of domination-type problems in graphs.Nordic Journal of Computing, 1(1):157–171, 1994

    Jan Arne Telle. Complexity of domination-type problems in graphs.Nordic Journal of Computing, 1(1):157–171, 1994. URL:https://www.cs.helsinki.fi/njc/ njc1.html

    1994

  61. [61]

    Thilikos, Maria Serna, and Hans L

    Dimitrios M. Thilikos, Maria Serna, and Hans L. Bodlaender. Cutwidth I: A linear time fixed parameter algorithm.Journal of Algorithms, 56(1):1–24, 2005. doi: 10.1016/j.jalgor.2004.12.001

    work page doi:10.1016/j.jalgor.2004.12.001 2005

  62. [62]

    Urschel and Jake Wellens

    John C. Urschel and Jake Wellens. Testing gapk-planarity is NP-complete.Informa- tion Processing Letters, 169:106083, 2021.doi:10.1016/j.ipl.2020.106083

    arXiv 2021

  63. [63]

    The structure of graphs not admitting a fixed immersion.Journal of Combinatorial Theory, Series B, 110:47–66, 2015.doi:10.1016/j.jctb.2014

    Paul Wollan. The structure of graphs not admitting a fixed immersion.Journal of Combinatorial Theory, Series B, 110:47–66, 2015.doi:10.1016/j.jctb.2014. 07.003

    work page doi:10.1016/j.jctb.2014 2015

  64. [64]

    Wood and Jan Arne Telle

    David R. Wood and Jan Arne Telle. Planar decompositions and the crossing number of graphs with an excluded minor.The New York Journal of Mathematics, 13:117–146,

  65. [1985]

    URL:https://dl.acm.org/doi/abs/10.5555/21936.25446

    arXiv

  66. [2007]

    URL:https://nyjm.albany.edu/j/2007/13-8.html. 69

    2007