Pith. sign in

REVIEW 2 major objections 4 minor 29 references

Parameterized Algorithms for Book Embedding Problems

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read Book thickness is fixed-parameter tractable under vertex cover

desk verdict First real FPT results for book thickness beyond k=2; proofs hold up, with only minor kernel-size imprecision and a casual geometric step. read the letter →

arxiv 1908.08911 v1 pith:PWBI2HTE submitted 2019-08-23 cs.DS

Sujoy Bhore , Robert Ganian , Fabrizio Montecchiani , Martin Nöllenburg This is my paper · ORCID
classification cs.DS
keywords bookembeddingfixed-parametertractabilityvertexcovernumberpathwidthkernelizationvisibilitygraphdrawing
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 establishes that two NP-complete book embedding problems become tractable when the input graph is structurally simple. For graphs with a vertex cover of size $\tau$, both Fixed-Order Book Thickness and Book Thickness admit fixed-parameter algorithms, meaning they run in time linear in the graph size times a factor that depends only on $\tau$; the fixed-order problem is also fixed-parameter tractable when the pathwidth of the given vertex order is the parameter. In ordinary terms, once a small set of vertices touches every edge, or a narrow memory window along the spine suffices, the number of pages can be decided efficiently rather than by brute force. The algorithms are constructive: they return a book embedding that uses the minimum number of pages under the given order whenever one exists. These are the first fixed-parameter algorithms for the fixed-order problem and the first for general Book Thickness with more than two pages.

What carries the argument

The mechanism carrying the argument is record-based dynamic programming with interchangeability: the state is not the full page assignment but a bounded-size visibility record, and the interchangeability lemmas (Lemma 1 for visibility matrices, Lemma 4 for visibility vectors) guarantee that storing one arbitrarily chosen assignment per record is safe. This bounds the state space by $2^{O(\tau^3)}$ for the vertex-cover parameterization and by $(\kappa+2)^{O(\kappa^2)}$ for the pathwidth parameterization, yielding the FPT running times. For the unfixed-order variant, the load-bearing mechanism is kernelization by type counting: vertices outside the cover are classified by their neighbor set, and classes with more than $2k\tau+2$ vertices are reduced without changing whether a $k$-page embedding exists.

What would settle it

Search for a graph, a vertex order, and two distinct partial page assignments that yield identical visibility records (identical matrices for every snapshot position in Section 3.1, or identical vectors for every guard in Section 3.2) but for which one assignment admits a crossing-free completion to $k$ pages and the other does not; such a pair would refute Lemma 1 or Lemma 4 and invalidate the FPT bounds.

Watch

Extended reading notes

Core claim

The central discovery is that exponentially many partial page assignments can be compressed into a bounded number of equivalence classes without losing future options. In the vertex-cover algorithm, each record is a visibility matrix—a table recording which cover vertices are reachable from a given vertex on each page without crossing an already assigned edge—together with snapshots at the positions immediately after each cover vertex; Lemma 1 proves that any two assignments with identical records behave identically in all future extension steps. In the pathwidth algorithm, each record is a visibility vector whose $p$-th entry is the important guard for page $p$, the nearest guard whose edge on that page blocks the view; Observation 3 shows this single guard fully determines which vertices remain visible, and Lemma 4 proves the same interchangeability. For Book Thickness without a fixed order, the paper kernelizes: keeping only $2k\tau+2$ vertices of each type (same neighbor set inside the cover) preserves the answer, and an embedding of the reduced graph extends to the original.

Load-bearing premise

The load-bearing premise is that two partial page assignments producing identical visibility records are interchangeable for every future extension; if the concrete edge-to-page mapping ever influenced future possibilities beyond the record, the compression would lose soundness.

Editorial extensions

If this is right

  • A minimum-page book embedding of an $n$-vertex graph of vertex cover number $\tau$ can be computed in $2^{O(\tau^3)} \cdot n$ time.
  • Fixed-Order Book Thickness with an order of pathwidth $\kappa$ can be solved in $n \cdot \kappa^{O(\kappa^2)}$ time, even when $\kappa$ is much smaller than the vertex cover number.
  • Book Thickness is fixed-parameter tractable in the vertex cover number, via a kernel of $O(k\tau)$ vertices that preserves embeddability.
  • All three algorithms return a valid $k$-page book embedding whenever one exists, so they solve the search and optimization versions, not just the decision problem.
  • These are the first fixed-parameter algorithms for the fixed-order problem, and the first for Book Thickness that allow more than two pages.

Reading between the lines

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

  • If the important-guard characterization survives a bounded crossing budget, the same right-to-left dynamic program could likely run in $n \cdot (\kappa+c)^{O(\kappa^2)}$ time for embeddings with at most $c$ crossings per page, extending the paper's own suggested future direction.
  • The interchangeability principle suggests a route to a bounded-treewidth algorithm, provided one can replace the spine's guards with a treewidth analogue of the important-guard observation, since a vertex can then be shielded by edges spanning several bags.
  • The kernel's dependence on neighbor sets suggests that other parameters bounding the number of distinct adjacency types, such as bounded neighborhood diversity, may also yield FPT algorithms for Book Thickness by the same type-counting argument.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies the parameterized complexity of two NP-complete book embedding problems. For Fixed-Order Book Thickness, Theorem 1 provides an algorithm running in 2^{O(τ^3)}·n when parameterized by the vertex cover number τ, and Theorem 2 provides an algorithm running in n·κ^{O(κ^2)} when parameterized by the pathwidth κ of the fixed vertex order. For Book Thickness, Theorem 3 gives a kernelization parameterized by τ, with total running time τ^{τ^{O(τ)}} + 2^τ·n. All three algorithms output a witness embedding if one exists. The proofs are based on dynamic programming over visibility matrices and visibility vectors, with interchangeability lemmas showing that partial page assignments with identical visibility records are equivalent for all future extensions, and a kernelization using page-equivalence classes of vertices outside a vertex cover.

Significance. The results are significant and timely. They provide the first FPT algorithms for Fixed-Order Book Thickness and the first FPT algorithm for Book Thickness for general values of k, making progress on a question of Dujmović and Wood about bounded-treewidth graphs. The visibility-based DP abstraction is elegant and the interchangeability lemmas are the right technical tool; the algorithms are also constructive and output witnesses. The kernelization is simple and uses a clean K_{2,3} obstruction argument. On close reading, the central DP correctness arguments are sound. The caveats are local: a pigeonhole bound in the kernelization proof is misstated, one geometric insertion step is informal, and some notation is sloppy. None of these issues affects the main FPT claims, and all are easily repairable.

major comments (2)
  1. [Section 4, Theorem 3 Claim] The pigeonhole step is incorrect as written. With |V_U\{v}| ≥ 2kτ+1 vertices partitioned into at most k^τ page-equivalence classes, one cannot conclude that three vertices are page-equivalent; for example, k=τ=10 gives 41 vertices and up to 10^10 classes. The argument requires |V_U\{v}| > 2k^τ, so the threshold should be |V_U| ≥ 2k^τ+2. Consequently the kernel size is O(2^τ k^τ), not O(kτ) as stated. The FPT bound in Theorem 3 remains valid after this correction, but the proof and the stated kernel size need to be fixed.
  2. [Section 4, Theorem 3 Claim (embedding extension)] The extension of a k-page book embedding by inserting v next to u1 and routing each new edge vw 'arbitrarily close' to u1w is informal. A rigorous justification is needed: because u1 has at most one edge on each page, each page contains at most one new edge incident to v, and that edge can be drawn in the same face of the existing page as u1w; since v and u1 are consecutive on the spine, the small connecting segment crosses no edge. Please spell this out and state explicitly whether v is inserted to the left or right of u1.
minor comments (4)
  1. [Section 3.1] Superscripts are missing in several bounds: 'ττ^2' should be τ^{τ^2}, '2τ^3+τ^2' should be 2^{τ^3+τ^2}, and 'ττ' in the runtime should be τ^τ.
  2. [Section 3.2, Lemma 4] The proof is too compressed. It should state explicitly that the transition from Q_i to Q_{i-1} is a deterministic function of the visibility vectors in a record and the assignment β of F_{i-1}, so that two partial assignments with the same record are interchangeable for validity and for the updated record. This is the key safety property of the representative Λ_i and deserves a direct statement.
  3. [Section 3.2, base case] When computing Q_0 from Q_1, the rule 'if v_{i-1}∈P^*_i then ω'=(ω_2,...,ω_m)' yields an empty tuple when P^*_1={v_0}; the paper should clarify that v_0's visibility vector is vacuously all-⋄ and that an empty record for Q_0 is intended, or add a special-case initialization for Q_0.
  4. [Section 4, Theorem 3] The brute-force expression O(kτ!·k^{kτ}) is unclear. Since the kernel has N = O(2^τ k^τ) vertices, the enumeration should be stated as O(N!·k^{O(N^2)}), which evaluates to τ^{τ^{O(τ)}}.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all three FPT results are proved from definitions and standard external lemmas.

full rationale

This is a self-contained algorithms paper with no fitted parameters, no empirical predictions, and no load-bearing self-citation. The three main theorems are proved directly: Theorem 1 and Theorem 2 use dynamic programming on visibility records, and the key interchangeability claims (Lemma 1 and Lemma 4) are proven combinatorially rather than assumed. Theorem 3 is a kernelization whose equivalence proof relies on the standard external fact that K_{2,3} has no 1-page book embedding, cited to Bernhart and Kainen, and on a pigeonhole argument over page-equivalent vertices. The citation to the authors' own earlier work in the introduction is contextual and not needed for any proof step. The minor imprecision in the kernel size bound, where the stated O(k tau) hides the 2^tau factor from the number of types, is absorbed by the stated f(tau) brute-force time and does not affect the correctness or the FPT claim. No equation is used as both input and output, and no known result is renamed as a new contribution.

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

No free parameters or invented entities appear. The results are pure complexity-theoretic theorems; the only inputs are graph, order, integer k, and structural parameters. The proofs rely on standard background results listed above.

assumptions (5)
  • standard math On a single page, a set of edges is crossing-free exactly when no two edges have alternating endpoints u ≺ w ≺ v ≺ x.
    This is the combinatorial definition of book embedding given in Section 1 and is the basis for all visibility arguments.
  • standard math K_{2,3} does not admit a 1-page book embedding.
    Used in Theorem 3's kernelization to conclude each page-equivalent vertex has at most one edge per page; follows from the fact that 1-page book embeddings are exactly outerplanar graphs.
  • standard math A minimum vertex cover of size tau can be computed in O(2^tau + tau·n) time.
    Cited to Chen, Kanj, and Xia [6] and used as preprocessing in all three algorithms.
  • standard math Pathwidth of (G,≺) equals the maximum guard set size as defined in Section 2.
    Equivalent to vertex separation pathwidth, cited to Kinnersley [21]; this is the parameter definition used in Theorem 2.
  • standard math Complete bipartite graphs K_{k,h} with h > k(k-1) have book thickness k.
    Cited to Bernhart and Kainen [4]; used only to argue tightness of Observation 1 and Lemma 2, not load-bearing for correctness.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parameterized Algorithms for Book Embedding Problems." pith.science (2026). https://pith.science/paper/PWBI2HTE

@misc{pith2026190808911,
  author       = {Pith},
  title        = {Pith review of: Parameterized Algorithms for Book Embedding Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PWBI2HTE}},
  note         = {Machine review of arXiv:1908.08911}
}
read the original abstract

A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called Fixed-Order Book Thickness, or not fixed, called Book Thickness. Both problems are known to be NP-complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order.

Figures

Figures reproduced from arXiv: 1908.08911 by the authors.

Figure 1
Figure 1. (a) A planar graph G with book thickness two. (b) A 2-page book embedding of G. (c) A linear order of G such that its fixed-order book thickness is three (and the corresponding 3-page book embedding). most four. Several other bounds are known for special graph families, for instance planar graphs with vertex degree at most four have book thickness two [3], while graphs of treewidth w > 2 have book thickness w + 1 [1… view at source ↗
Figure 2
Figure 2. A partial 2-page book embedding of a graph G with a vertex cover C of size 7. The visibilities of vertices in C (squares) from u2 are marked by dashed edges (left). Corresponding visibility matrix M2(2, α, s) (right). compute for each individual vertex in left-to-right order. Let c1 ≺ . . . ≺ cτ be the ordering of vertices of C, and let u1 ≺ . . . ≺ un−τ be the ordering of vertices of U. In order to formalize our re… view at source ↗
Figure 3
Figure 3. An assignment of the edges of Si to a page p, where the edge vcvd is the (α, i, p)- important edge of va. Any vertex w with vc ≺ w ≺ va is visible to va, and any vertex w 0 ≺ vc is not visible to va. κ. The algorithm performs a dynamic programming procedure on the vertices v1, v2, . . . , vn of the input graph G in right-to-left order along ≺. For technical reasons, we initially add a vertex v0 of degree 0 to G and … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 8 canonical work pages

  1. [1]

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

    doi:10.7155/jgaa.00457 2018

  2. [2]

    Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page draw- ings of graphs with bounded treewidth. J. Graph Algorithms Appl. 22(4), 577–606 (2018). https://doi.org/10.7155/jgaa.00479

    doi:10.7155/jgaa.00479 2018

  3. [3]

    Algorithmica 75(1), 158–185 (2016)

    Bekos, M.A., Gronemann, M., Raftopoulou, C.N.: Two-page book em- beddings of 4-planar graphs. Algorithmica 75(1), 158–185 (2016). https://doi.org/10.1007/s00453-015-0016-8

    work page doi:10.1007/s00453-015-0016-8 2016

  4. [4]

    Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Comb. Theory, Ser. B 27(3), 320–331 (1979). https://doi.org/10.1016/0095-8956(79)90021-2

    doi:10.1016/0095-8956(79)90021-2 1979

  5. [5]

    Binucci, C., Di Giacomo, E., Hossain, M.I., Liotta, G.: 1-page and 2-page drawings with bounded number of crossings per edge. Eur. J. Comb. 68, 24–37 (2018). https://doi.org/10.1016/j.ejc.2017.07.009

    work page doi:10.1016/j.ejc.2017.07.009 2018

  6. [6]

    Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Com- put. Sci. 411(40-42), 3736–3756 (2010). https://doi.org/10.1016/j.tcs.2010.06.026

    doi:10.1016/j.tcs.2010.06.026 2010

  7. [7]

    Chung, F., Leighton, F., Rosenberg, A.: Embedding graphs in books: A layout problem with applications to VLSI design. SIAM J. Alg. Discr. Meth. 8(1), 33–58 (1987). https://doi.org/10.1137/0608002

    doi:10.1137/0608002 1987

  8. [8]

    Springer (2015)

    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

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

Show all 29 references
  1. [9]

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

    2012

  2. [10]

    Texts in Computer Science, Springer (2013)

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

    2013 doi

  3. [11]

    Discrete Math

    Dujmovi´ c, V., Wood, D.R.: On linear layouts of graphs. Discrete Math. Theor. Comput. Sci. 6(2), 339–358 (2004)

    2004

  4. [12]

    Discrete Computat

    Dujmovic, V., Wood, D.R.: Graph treewidth and geometric thick- ness parameters. Discrete Computat. Geom. 37(4), 641–670 (2007). https://doi.org/10.1007/s00454-007-1318-7

    2007 doi

  5. [13]

    Discrete Math

    Dujmovi´ c, V., Wood, D.R.: On the book thickness of k-trees. Discrete Math. Theor. Comput. Sci. 13(3), 39–44 (2011) 13

    2011

  6. [14]

    In: Algorithms and Computation (ISAAC’08)

    Fellows, M.R., Lokshtanov, D., Misra, N., Rosamond, F.A., Saurabh, S.: Graph layout problems parameterized by vertex cover. In: Algorithms and Computation (ISAAC’08). pp. 294–305 (2008). https://doi.org/10.1007/978-3-540-92182-0 28

    2008 doi

  7. [15]

    Discrete Math

    Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2), 77–100 (2015)

    2015

  8. [16]

    Ganian, R., Ordyniak, S.: The complexity landscape of decom- positional parameters for ILP. Artif. Intell. 257, 61–71 (2018). https://doi.org/10.1016/j.artint.2017.12.006

    2018 doi

  9. [17]

    Discrete Appl

    Ganley, J.L., Heath, L.S.: The pagenumber ofk-trees isO(k). Discrete Appl. Math. 109(3), 215–221 (2001). https://doi.org/10.1016/S0166-218X(00)00178-5

    2001 doi

  10. [18]

    Gutin, G.Z., Jones, M., Wahlstr¨ om, M.: The mixed Chinese postman problem parameterized by pathwidth and treedepth. SIAM J. Discrete Math. 30(4), 2177– 2205 (2016). https://doi.org/10.1137/15M1034337

    2016 doi

  11. [19]

    Haslinger, C., Stadler, P.F.: RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties. Bull. Math. Biol. 61(3), 437–467 (1999). https://doi.org/10.1006/bulm.1998.0085

    1999

  12. [20]

    In: Bari, R.A., Harary, F

    Kainen, P.C.: Some recent results in topological graph theory. In: Bari, R.A., Harary, F. (eds.) Graphs and Combinatorics. pp. 76–108. Springer (1974). https://doi.org/10.1007/BFb0066436

    1974 doi

  13. [21]

    Kinnersley, N.G.: The vertex separation number of a graph equals its path- width. Inf. Process. Lett. 42(6), 345–350 (1992). https://doi.org/10.1016/0020- 0190(92)90234-M

    1992 doi

  14. [22]

    In: Gaspers, S., Walsh, T

    Lodha, N., Ordyniak, S., Szeider, S.: Sat-encodings for special treewidth and pathwidth. In: Gaspers, S., Walsh, T. (eds.) Theory and Applications of Sat- isfiability Testing (SAT’17). LNCS, vol. 10491, pp. 429–445. Springer (2017). https://doi.org/10.1007/978-3-319-66263-3 27

    2017 doi

  15. [23]

    In: Brankovic, L., Ryan, J., Smyth, W

    Mallach, S.: Linear ordering based MIP formulations for the vertex separation or pathwidth problem. In: Brankovic, L., Ryan, J., Smyth, W. (eds.) Combina- torial Algorithms (IWOCA’17). LNCS, vol. 10765, pp. 327–340. Springer (2017). https://doi.org/10.1007/978-3-319-78825-8 27

    2017 doi

  16. [24]

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

    2012 doi

  17. [25]

    In: 4th Southeastern Conference on Combinatorics, Graph Theory and Computing

    Ollmann, L.T.: On the book thicknesses of various graphs. In: 4th Southeastern Conference on Combinatorics, Graph Theory and Computing. vol. 8, p. 459 (1973)

    1973

  18. [26]

    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

  19. [27]

    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

  20. [28]

    In: Finkel, A., Jantzen, M

    Unger, W.: The complexity of colouring circle graphs (extended ab- stract). In: Finkel, A., Jantzen, M. (eds.) Theoretical Aspects of Com- puter Science (STACS’92). LNCS, vol. 577, pp. 389–400. Springer (1992). https://doi.org/10.1007/3-540-55210-3 199

    1992 doi

  21. [29]

    Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36–67 (1989). https://doi.org/10.1016/0022-0000(89)90032-9 14 A Missing Proofs of Section 3 Observation 2 If for all s∈ S it holds that Rn−τ(s) =∅, then (G,≺,k ) is a NO-instance of Fixed-Order...

    1989 doi

Pith tools

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