Mixed Linear Layouts: Complexity, Heuristics, and Experiments

Fabian Klute; Martin N\"ollenburg; Philipp de Col

REVIEW 2 major objections 4 minor 15 references

Mixed Linear Layouts: Complexity, Heuristics, and Experiments

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 The paper proves that recognizing 2-stack 1-queue layouts is NP-complete, settling a mixed linear layout complexity question, and presents a heuristic that reduces conflicts.

desk verdict The heuristic and experiments are solid and honest, but the main NP-completeness proof has a gap in the induction step that leaves Theorem 1 unproven as written. read the letter →

arxiv 1908.08938 v1 pith:MB2DBDWQ submitted 2019-08-23 cs.DS

Philipp de Col , Fabian Klute , Martin Nöllenburg This is my paper · ORCID

classification cs.DS MSC 68Q1768R10

keywords mixedlinearlayoutsstackqueue2-stack1-queueNP-completenessgraphdrawingconflictminimizationheuristics

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 proves that deciding whether a graph admits a layout with two stack pages and one queue page is NP-complete, closing the complexity question for a natural mixed layout model. It also shows that NP-completeness is preserved when an extra stack or queue page is added to a fixed-order layout problem. On the algorithmic side, the paper introduces the first heuristic aimed directly at minimizing crossings and nestings in 1-stack 1-queue layouts, using counters to estimate future conflicts. Experiments on random graphs, planar bipartite graphs, and tree-like graphs show the new heuristic matches or outperforms two established book-embedding heuristics adapted to mixed layouts, with Delaunay triangulations as the main exception.

What carries the argument

The argument for NP-completeness rests on a rigid gadget: the double-K8, formed by identifying two vertices of two K8 cliques and adding an edge between two outer vertices. Exhaustive search over all vertex orders establishes three structural observations about 2-stack 1-queue layouts of K8 and double-K8, namely that certain longest edges must lie in the stack pages, certain edges must lie in the queue page, and only the first and last vertices of two copies can interleave. These observations force the input graph's vertices to be placed between the outer vertices of the two gadgets, turning the question of a 2-stack 1-queue layout into the NP-complete question of a 2-stack layout. The heuristic uses a different mechanism: while scanning vertices left to right it inserts edges into tentative stack and queue data structures, keeps a crossing counter and a nesting counter for each edge, and assigns each edge to the page with the lower estimated future conflict cost.

What would settle it

Run an independent exhaustive search over all 8! vertex orders and all page assignments of K8 to check Observation 1's claims that v1v3 and v6v8 are always in the queue page and that the longest edges are in the stacks; any counterexample would invalidate Theorem 1's gadget.

Watch

Extended reading notes

Core claim

The central claim is that recognizing 2-stack 1-queue layouts is NP-complete. The proof reduces from the NP-complete 2-stack layout problem by attaching a specially constructed graph to an arbitrary input graph; a gadget built from two copies of K8 (a double-K8) forces any valid layout to confine the input graph's vertices between two outer vertices, so that the input edges must all lie in the stack pages. A second result shows that if a fixed-order s-stack q-queue recognition problem is NP-complete, then adding one more stack or queue page keeps it NP-complete. The paper also claims that its stack-queue page assignment heuristic, which processes vertices left to right and assigns each edge by comparing estimated future crossing and nesting counts, produces fewer or comparable conflicts per edge than the adapted eLen and ceilFloor heuristics on most benchmark graph classes, the exception being larger Delaunay triangulations where ceilFloor is better.

Load-bearing premise

The NP-completeness proof depends on exhaustive computer search over all vertex orders of K8 and double-K8; if that search is incomplete or incorrectly implemented, the structural observations and the reduction built on them could fail.

Editorial extensions

If this is right

Unless P = NP, there is no polynomial-time algorithm that decides whether a given graph admits a 2-stack 1-queue layout.
The reduction's gadget may generalize to s-stack 1-queue layouts for s > 2 if larger rigid cliques are found, as the authors suggest.
The stack-queue heuristic runs in O(m^2) time, matching eLen and ceilFloor, so it can be used in practice without extra cost.
For random graphs, planar bipartite graphs, and 3-trees, the new heuristic wins on most instances; for Delaunay triangulations, ceilFloor wins on larger instances.
The heuristic can be generalized to arbitrary numbers of stack and queue pages.

Reading between the lines

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

Because the exhaustive-search observations are the load-bearing part of the NP-completeness proof, a natural next step is to independently re-verify them with a different search implementation; if any observation is false, Theorem 1 would need a different gadget.
The heuristic's future-conflict estimation could be combined with vertex-order heuristics that specifically reduce nestings, since the authors note that specialized queue-oriented order heuristics are missing.
The exception of Delaunay triangulations suggests that a hybrid algorithm could select between stack-queue and ceilFloor based on graph properties such as average degree or number of triangles.
The fixed-order NP-completeness preservation result means that SAT-based layout tools cannot rely on adding pages to make the page-assignment subproblem tractable.

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.

Desk Editor's Note

read the letter

Colleague,

The paper has two distinct parts that should not be graded together. The heuristic and experimental study are useful and honest; the complexity section has a serious gap that, as written, leaves Theorem 1 unproven.

What's new and good: the stack-queue page assignment heuristic is, to my knowledge, the first targeted at mixed 1-stack 1-queue layouts. The idea of keeping crossing and nesting counters while processing vertices in order, and using a look-ahead term (0.5 per active edge) to decide page assignment, is sensible and runs in O(m^2). The experiments compare fairly against adapted eLen and ceilFloor across random graphs, Delaunay triangulations, planar bipartite graphs, and 2/3-trees, and report winners per instance plus error bands. They also report the Delaunay exception honestly, though the abstract overstates the case by omitting it. Theorem 2, the page-addition monotonicity result, is a clean structural observation with a plausible proof.

The soft spot is Theorem 1. Lemma 2 only establishes that the designated vertex u lies between the two outer vertices w1 and w2, using edges w1u and w2u. The converse direction then asserts, "As for u in Lemma 2, we find that w1≺v≺w2 for every neighbor v of u," and inducts over all of G. But a neighbor v is not incident to w1 or w2, so Lemma 2 cannot be applied to v. No lemma in the appendix supplies that step. This is not merely a connectivity issue; even for connected G, the induction does not follow. Without forcing every vertex of G into the w1–w2 interval, the argument that all edges of G are nested by the two queue edges collapses, and the reduction from 2-stack layout is not established. The result may be true and fixable—perhaps with a stronger gadget or a case analysis—but the written proof does not prove it.

The exhaustive-search observations for K8 and double-K8 in Appendix A are a lesser worry: code is provided, but the search space and completeness criteria are not documented in the paper. That's a minor fix. The heuristic's 0.5 weight is a free parameter, though the paper does not tune it to make claims, so that is fine.

If I were editor, I would send it to review: the heuristic work deserves publication, and the complexity result is worth an expert look. But the referee must force a rewrite of Theorem 1's proof. This is a revise-and-resubmit, not a reject.

Referee Report

2 major / 4 minor

Summary. The paper studies mixed linear layouts with s stack pages and q queue pages. It claims two complexity results: (1) deciding whether a graph admits a 2-stack 1-queue layout is NP-complete, and (2) a fixed-vertex-order mixed layout recognition problem remains NP-complete under addition of one stack or one queue page. The paper also proposes a new O(m^2) page-assignment heuristic for minimizing crossings and nestings in 1-stack 1-queue layouts, and evaluates it against two adapted book-drawing heuristics on random graphs, Delaunay triangulations, planar bipartite graphs, 2-trees, and 3-trees.

Significance. If the NP-completeness theorem is correctly established, it is a meaningful contribution to the sparse literature on mixed linear layout complexity. The heuristic is, to the authors' knowledge, the first targeted at conflict minimization in mixed 1-stack 1-queue layouts, and the experimental study is careful, with code provided, multiple vertex-order heuristics considered, and six benchmark classes. The reported improvements over adapted book-drawing heuristics on most classes (with Delaunay triangulations as an exception) are plausible and useful. However, the central NP-completeness proof contains a serious unsupported step, and the structural observations used in the reduction are verified only by an undescribed exhaustive search, so the complexity claim is not established as written.

major comments (2)

[Section 2, proof of Theorem 1] The converse direction contains an unsupported inductive step. Lemma 2 establishes only that the distinguished vertex u lies between w1 and w2 in the constructed gadget. The proof then asserts 'As for u in Lemma 2, we find that w1≺v≺w2 for every neighbor v∈V of u' and proceeds by induction over V. Lemma 2, however, applies only to the special vertex u, which is incident to both w1 and w2; an arbitrary neighbor v of u is not incident to w1 or w2, so the lemma cannot be invoked for v. No lemma in Appendix A supplies a propagation argument showing that a neighbor of a vertex known to lie between w1 and w2 must itself lie between them. Consequently, even for connected G the step from u to its neighbors is a non sequitur, and for disconnected G the induction cannot reach vertices outside the component of u. Because this step is what forces all edges of G into the two stack pages, the NP-completeness proof as written does not establish the result. The authors should either prove a suitable stronger gadget lemma or restrict the reduction to connected graphs and justify the propagation.
[Appendix A, Observations 1-3] The rigidity properties of K8 and double-K8 layouts that underpin Lemma 2 and hence Theorem 1 are asserted to follow from exhaustive search, with only a link to source code provided. The manuscript does not describe the search space (e.g., whether all vertex orders or all page assignments are enumerated), the pruning rules, or the verification procedure. Since these observations are load-bearing for the NP-completeness reduction, the paper should include a detailed description of the exhaustive search parameters and the exact statements verified, or replace them with human-checkable proofs.

minor comments (4)

[Abstract and Section 3] The abstract states experiments 'for the cases, q = 1', which appears to be a typo; it should read 'for the case s, q = 1'.
[Section 3, algorithm description] The description of the stack and queue data structures does not specify how the notions 'edges on top of e in S' and 'edges in front of e in Q' are defined when e is removed from an interior position rather than from the top/front. The authors should clarify whether these counts refer to the current state of the data structure after all insertions up to the right endpoint of e, and how removals from interior positions are implemented.
[Section 2, proof of Theorem 2(ii)] In the second reduction, the claim that 'no edge between vertices of M can be on a queue page' is not justified in the text; the argument should state explicitly that every queue page already contains an edge from some Mi that nests each M-edge.
[Appendix B, Figures 4 and 5] The captions of Figures 4 and 5 do not mention that the vertical axis is 'conflicts per edge'; adding this would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the NP-completeness reductions use independent exhaustive-search observations and known NP-complete sources, and the heuristic is evaluated against external baselines without fitted parameters.

full rationale

The paper's central claims are not circular. Theorem 1 reduces from the known NP-complete 2-stack layout problem and relies on Observations 1-3 in Appendix A, which are obtained by exhaustive search over all orders of K8 and double-K8 gadgets with source code provided; these are independent computational checks, not fitted parameters or renamed inputs. The gadget lemmas are then used to deduce structural constraints on 2-stack 1-queue layouts, and the reverse direction of the reduction follows from those constraints rather than from assuming the desired conclusion. Theorem 2 reduces from a stated NP-complete fixed-order layout problem using explicit gadget constructions with correctness arguments. The heuristic section introduces a hand-chosen tie-breaking constant of 0.5, but this is an algorithmic design choice and is not calibrated to any benchmark data; no claim in the experiment is derived from the heuristic's own output. The experimental evaluation compares the new stack-queue heuristic against the external baselines eLen and ceilFloor on independently generated graph classes, measuring conflict counts directly. While the induction step in Theorem 1 from the distinguished vertex u to all neighbors of u is arguably under-justified as a proof step, that is a correctness gap rather than a circular reduction: the proof does not define the target property in terms of itself or fit a parameter to force the claim. No load-bearing step in the paper reduces by construction to its own inputs, and no central premise depends solely on a self-citation.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The central claims rest on cited NP-completeness of subhamiltonian graphs, computer-verified gadget observations, and an implicit connectivity assumption in the proof of Theorem 1. The heuristic has one hand-chosen weight, but no data-fitted parameters.

free parameters (1)

look-ahead weight in stack-queue page assignment = 0.5
Hand-chosen constant in the heuristic's decision rule (c(e)+0.5*se vs n(e)+0.5*qe). Not fitted to data, not tuned; the heuristic's comparative performance could depend on this value.

assumptions (3)

domain assumption Subhamiltonian (2-stack layout) recognition is NP-complete
Used as the source problem in the reduction for Theorem 1, citing Bernhart and Kainen [1] and Chung et al. [2].
domain assumption Exhaustive-search observations (Appendix A, Observations 1-3) about K8 and double-K8 layouts are complete and correct
These computational verifications underpin Lemmas 1-2 and Theorem 1. The paper provides source code but no certificate or independent machine-checked proof.
ad hoc to paper The input graph G in Theorem 1 is assumed connected for the induction step
The proof states 'by induction we find for all v' in V that w1 < v' < w2'; this propagation requires connectivity, which is not stated or justified in the reduction.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Mixed Linear Layouts: Complexity, Heuristics, and Experiments." pith.science (2026). https://pith.science/paper/MB2DBDWQ

@misc{pith2026190808938,
  author       = {Pith},
  title        = {Pith review of: Mixed Linear Layouts: Complexity, Heuristics, and Experiments},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MB2DBDWQ}},
  note         = {Machine review of arXiv:1908.08938}
}

abstract

A $k$-page linear graph layout of a graph $G = (V,E)$ draws all vertices along a line $\ell$ and each edge in one of $k$ disjoint halfplanes called pages, which are bounded by $\ell$. We consider two types of pages. In a stack page no two edges should cross and in a queue page no edge should be nested by another edge. A crossing (nesting) in a stack (queue) page is called a conflict. The algorithmic problem is twofold and requires to compute (i) a vertex ordering and (ii) a page assignment of the edges such that the resulting layout is either conflict-free or conflict-minimal. While linear layouts with only stack or only queue pages are well-studied, mixed $s$-stack $q$-queue layouts for $s,q \ge 1$ have received less attention. We show NP-completeness results on the recognition problem of certain mixed linear layouts and present a new heuristic for minimizing conflicts. In a computational experiment for the case $s, q = 1$ we show that the new heuristic is an improvement over previous heuristics for linear layouts.

Figures

Figures reproduced from arXiv: 1908.08938 by the authors.

**Figure 2.** How many times each algorithm obtained the fewest conflicts in percent. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Illustration of the reduction in Theorem 2 [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Number of conflicts per edge for the three heuristics and six benchmark [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

**Figure 5.** Figure 5: Number of conflicts per edge for the three heuristics and six benchmark [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 6 canonical work pages

[1]

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
[2]

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
[3]

Discrete Applied Mathematics 122(1-3), 93–115 (2002)

Cimikowski, R.J.: Algorithms for the ﬁxed linear crossing num- ber problem. Discrete Applied Mathematics 122(1-3), 93–115 (2002). https://doi.org/10.1016/S0166-218X(01)00314-6

work page doi:10.1016/s0166-218x(01)00314-6 2002
[4]

CoRR abs/1904.04791 (2019)

Dujmovic, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. CoRR abs/1904.04791 (2019)

arXiv 2019
[5]

Discrete Math

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

work page 2004
[6]

Discrete & Computational Geometry 13, 459–468 (1995)

de Fraysseix, H., de Mendez, P.O., Pach, J.: A left-ﬁrst search algorithm for planar graphs. Discrete & Computational Geometry 13, 459–468 (1995). https://doi.org/10.1007/BF02574056

doi:10.1007/bf02574056 1995
[7]

In: Workshop on Information Technologies - Applications and Theory (ITAT) (2004)

He, H., S´ ykora, O.: New circular drawing algorithms. In: Workshop on Information Technologies - Applications and Theory (ITAT) (2004)

work page 2004
[8]

Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math. 5(3), 398–412 (1992). https://doi.org/10.1137/0405031

doi:10.1137/0405031 1992

Show all 15 references

[9]

Heath, L.S., Rosenberg, A.L.: Laying out graphs using queues. SIAM J. Comput. 21(5), 927–958 (1992). https://doi.org/10.1137/0221055

1992 doi
[11]

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
[12]

In: Frati, F., Ma, K.L

Pupyrev, S.: Mixed linear layouts of planar graphs. In: Frati, F., Ma, K.L. (eds.) Graph Drawing and Network Visualization (GD’17). LNCS, vol. 10692, pp. 197–
[13]

Memetic Computing 5(4), 255–274 (2013)

Satsangi, D., Srivastava, K., Srivastava, G.: K-page crossing number minimization problem: An evaluation of heuristics and its solution using GESAKP. Memetic Computing 5(4), 255–274 (2013). https://doi.org/10.1007/s12293-013-0115-5

2013 doi
[14]

In: STACS 88, 5th Annual Sym- posium on Theoretical Aspects of Computer Science, Bordeaux, France, February 11-13, 1988, Proceedings

Unger, W.: On the k-colouring of circle-graphs. In: STACS 88, 5th Annual Sym- posium on Theoretical Aspects of Computer Science, Bordeaux, France, February 11-13, 1988, Proceedings. pp. 61–72 (1988). https://doi.org/10.1007/BFb0035832

1988 doi
[15]

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 8 Philipp de Col, Fabian Klute, and Martin N¨ ollenburg A Omitted Proofs from Section 2 The following observations follow from exhaust...

1989 doi
[209]

https://doi.org/10.1007/978-3-319-73915-1 17

Springer (2018). https://doi.org/10.1007/978-3-319-73915-1 17

2018 doi

Pith tools

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

[1] [1]

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

[2] [2]

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

[3] [3]

Discrete Applied Mathematics 122(1-3), 93–115 (2002)

Cimikowski, R.J.: Algorithms for the ﬁxed linear crossing num- ber problem. Discrete Applied Mathematics 122(1-3), 93–115 (2002). https://doi.org/10.1016/S0166-218X(01)00314-6

work page doi:10.1016/s0166-218x(01)00314-6 2002

[4] [4]

CoRR abs/1904.04791 (2019)

Dujmovic, V., Joret, G., Micek, P., Morin, P., Ueckerdt, T., Wood, D.R.: Planar graphs have bounded queue-number. CoRR abs/1904.04791 (2019)

arXiv 2019

[5] [5]

Discrete Math

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

work page 2004

[6] [6]

Discrete & Computational Geometry 13, 459–468 (1995)

de Fraysseix, H., de Mendez, P.O., Pach, J.: A left-ﬁrst search algorithm for planar graphs. Discrete & Computational Geometry 13, 459–468 (1995). https://doi.org/10.1007/BF02574056

doi:10.1007/bf02574056 1995

[7] [7]

In: Workshop on Information Technologies - Applications and Theory (ITAT) (2004)

He, H., S´ ykora, O.: New circular drawing algorithms. In: Workshop on Information Technologies - Applications and Theory (ITAT) (2004)

work page 2004

[8] [8]

Heath, L.S., Leighton, F.T., Rosenberg, A.L.: Comparing queues and stacks as mechanisms for laying out graphs. SIAM J. Discrete Math. 5(3), 398–412 (1992). https://doi.org/10.1137/0405031

doi:10.1137/0405031 1992