Open Problems in Linear Graph Layouts

STACK NUMBER OF COMPLETE BIPARTITE GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine sn(K_m,n) for all m,n; in particular, determine the asymptotic leading constant of sn(K_n,n)/n.

Discussed in:

• Bernhart and Kainen, The Book Thickness of a Graph (1979).
• Muder, Weaver, and West, Pagenumber of Complete Bipartite Graphs (1988, introduction).
• Enomoto, Nakamigawa, and Ota, On the Pagenumber of Complete Bipartite Graphs (1997).
• West, Quack Number: Queue/Stack Decomposition (REGS 2010, comments following Question 2).
• Sperfeld, On the Page Number of Complete Odd-Partite Graphs (2013, Section 1).

Comments:

• For the balanced case, sn(K_n,n)≥⌈n/2⌉.
• Enomoto, Nakamigawa, and Ota proved sn(K_n,n)≤⌊2n/3⌋+1.
• For g(n):=min{m:sn(K_m,n)=n}, Enomoto, Nakamigawa, and Ota proved g(n)=n²/4+O(n^7/4).
• For every integer k with 2≤k≤6, sn(K_{k+1,⌊(k+1)²/4⌋+1})=k+1.

STACK NUMBER OF K-PLANAR GRAPHSESTIMATED DIFFICULTY: HARD

A graph is k-planar if it has a drawing in which every edge is crossed at most k times.

Problem. For every fixed integer k≥2, does there exist a constant c_k such that sn(G)≤c_k for every k-planar graph G?

Discussed in:

• Alam, Brandenburg, and Kobourov, On the Book Thickness of 1-Planar Graphs (2015 preprint, Section 5).
• Klawitter, Mchedlidze, and Nöllenburg, Experimental Evaluation of Book Drawing Algorithms (GD 2017, Section 1).
• Brandenburg, Book Embeddings of k-Map Graphs (2020 preprint, revised 2023, Section 5).
• Dujmović, Morin, and Yelle, Two Results on Layered Pathwidth and Linear Layouts (2021, Section 4).

Comments:

• Every n-vertex k-planar graph G satisfies sn(G)≤30(k+1)log₂n.
• 1-planar graphs have constant stack number.
• Optimal 2-planar graphs have bounded stack number, but this does not cover all 2-planar graphs.

STACK NUMBER OF OPTIMAL 1-PLANAR GRAPHSESTIMATED DIFFICULTY: EASY

An n-vertex 1-planar graph is optimal if it has the maximum possible number 4n−8 of edges.

Problem. Determine sn(G) for optimal 1-planar graphs G.

Asked in:

• Brandenburg, Embedding 1-Planar Graphs in Ten Pages (2023 preprint, Section 5).

Comments:

• Every optimal 1-planar graph has stack number at least 4, while every 1-planar graph has stack number at most 10.
• Brandenburg conjectured that every optimal 1-planar graph has stack number 4.

STACK NUMBER OF KLEIN-BOTTLE GRAPHSESTIMATED DIFFICULTY: HARD

A graph is projective-planar if it has nonorientable genus at most 1, is embeddable on the Klein bottle if it has nonorientable genus at most 2, and is toroidal if it has orientable genus at most 1. The Euler genus of an orientable surface of genus g is 2g, while the Euler genus of a nonorientable surface of genus h is h; thus the torus and the Klein bottle both have Euler genus 2.

Problem. Does there exist a constant c such that sn(G)≤c for every graph G embeddable on the Klein bottle?

Discussed in:

• Nakamoto and Nozawa, Book Embedding of Projective-Planar Graphs (2015).
• Ozeki, Nakamoto, and Nozawa, Book Embedding of Graphs on the Projective Plane (2019, Section 1).
• Wood, post on the claimed minor-closed bound (2024).

Comments:

• Planar graphs have stack number at most 4, projective-planar graphs at most 6, and toroidal graphs at most 7. Thus the Klein bottle is the first unresolved fixed-surface case and the only unresolved surface of Euler genus 2.
• Heath and Istrail stated an O(g) bound and described N-LAYOUT for graphs of nonorientable genus g. This would answer the problem affirmatively, but Ozeki, Nakamoto, and Nozawa report that the nonorientable argument cannot be verified.
• Blankenship claimed that every proper minor-closed graph class has bounded stack number. The proof uses the disputed fixed-surface result of Heath and Istrail, so it does not independently settle the Klein-bottle case.
• For orientable genus g, the maximum stack number is Θ(√g). This does not settle the problem: graphs of fixed nonorientable genus can have arbitrarily large orientable genus.

STACK NUMBER OF CARTESIAN PRODUCTSESTIMATED DIFFICULTY: HARD

Problem. Let K_n be the complete graph on n vertices. Determine sn(K_n□K_n) as a function of n. Characterize the graphs G for which sn(G□K₂)=sn(G), and those for which sn(G□K₂)=sn(G)+1.

Asked in:

• Chung, Leighton, and Rosenberg, Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design (1987, Section 3.7).
• West, Report on REGS on Extremal Problems in Combinatorics (2004, “Pagenumber of graphs”).

Comments:

• If H is bipartite and dispersable, then sn(G□H)≤sn(G)+Δ(H). Since K₂ is dispersable, sn(G)≤sn(G□K₂)≤sn(G)+1 for every graph G; hence the two values in the problem exhaust all possibilities.
• Let P_m and C_m denote the path and cycle on m vertices. For every m≥2, sn(P_m□K₂)=1. If T is a nonpath tree, then sn(T□K₂)=2, and for every m≥3, sn(C_m□K₂)=2. Thus paths realize equality, whereas nonpath trees and cycles realize an increase by one.
• For the d-dimensional hypercube, sn(Q_d)=max{d−1,1}. Since Q_d=Q_d−1□K₂, the stack number increases by one for every d≥3.
• The graph K_n□K_n is the n×n rook graph, equivalently the line graph of K_n,n. It has n² vertices and n²(n−1) edges. The density lower bound and the general edge upper bound give n−1≤sn(K_n□K_n)≤cn^3/2 for n≥3 and some absolute constant c.
• Under the restriction that the vertices of K_n□K_n occur row by row along the spine, every stack layout requires Ω(n^4/3) stacks. This lower bound does not apply to unrestricted vertex orders.

STACK NUMBER OF CARTESIAN POWERS OF ODD CYCLESESTIMATED DIFFICULTY: EASY

Let C_k be the cycle on k vertices. Its d-fold Cartesian power is C_k^□d=C_k□⋯□C_k, with d factors.

Problem. For every fixed odd integer k≥3, is sn(C_k^□d)=O(d) as d→∞?

Asked in:

• Geng, Hao, and Yang, On the Stack Layouts of Toroidal Grids (2026, Section 5).

Comments:

• For all integers m,n≥3, sn(C_m□C_n)=3.
• For every fixed even k, sn(C_k^□d)≤2d−1, so together with the density lower bound below the stack number is Θ(d). For k=4, the upper bound is exact: C₄^□d≅Q_2d and sn(Q_2d)=2d−1.
• For fixed odd k≥5, the current upper bound is 5·2^d−2−2; for k=3 it is 2^d−1.
• Density gives sn(C_k^□d)≥d−1+o(1) for fixed k.

STACK NUMBER OF BIPARTITE TOROIDAL GRAPHSESTIMATED DIFFICULTY: MEDIUM

A graph is toroidal if it has orientable genus at most 1.

Problem. Determine the stack number of bipartite toroidal graphs; the value is 3, 4, or 5.

Asked in:

• Nakamoto, Ota, and Ozeki, Book Embedding of Toroidal Bipartite Graphs (2012, introduction).

Comments:

• Every bipartite toroidal graph has stack number at most 5.
• Nonplanar bipartite toroidal graphs give the lower bound 3, and no example requiring more than 3 pages is known.

TWIST NUMBER OF PLANAR GRAPHSESTIMATED DIFFICULTY: EASY

A k-twist in a vertex order is a set of k pairwise crossing edges. The twist number twn(G) is the minimum, over all vertex orders of G, of the largest twist. Equivalently, twn(G)≤k−1 if and only if G is outer k-quasi-planar, meaning that it has a convex straight-line drawing with no k pairwise crossing edges.

Problem. Determine the twist number of planar graphs; the value is 3 or 4.

Asked in:

• Chaplick, Kryven, Liotta, Löffler, and Wolff, Beyond Outerplanarity (Computing in Geometry and Topology 2026, Question 18).

Comments:

• Every planar graph has stack number at most 4, and therefore twist number at most 4.
• Some planar graphs, including planar 3-trees, have twist number at least 3.
• For every graph G, twn(G)≤sn(G) and sn(G)=O(twn(G) log twn(G)).
• Among n-vertex graphs with twist number at most k, the maximum number of edges is n(n−1)/2 when n≤2k+1, and 2kn−(2k+1)k when n≥2k+1.

QUEUE NUMBER OF PLANAR GRAPHSESTIMATED DIFFICULTY: HARD

Problem. Determine the queue number of planar graphs; the value lies between 4 and 48.

Asked in:

• Heath, Leighton, and Rosenberg, Comparing Queues and Stacks as Machines for Laying Out Graphs (1992).
• Heath and Rosenberg, Laying Out Graphs Using Queues (1992).
• Demaine, Mitchell, and O’Rourke, The Open Problems Project, Problem 52.
• Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood, Planar Graphs Have Bounded Queue-Number (2020), Section 10, Open Problem 1.
• Bekos, Gronemann, and Raftopoulou, An Improved Upper Bound on the Queue Number of Planar Graphs (Algorithmica 2023, introduction).

Comments:

• A planar 3-tree requiring 4 queues supplies the best lower bound.
• Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood proved a 49-queue upper bound and state in Section 10 that their proof can be tweaked to give 48.
• The published claim of an upper bound of 42 has unresolved gaps, so 48 is retained here.

QUEUE NUMBER OF BIPARTITE PLANAR GRAPHSESTIMATED DIFFICULTY: HARD

Problem. Determine the queue number of bipartite planar graphs; the value lies between 3 and 28.

Asked in:

• Bekos, Gronemann, and Raftopoulou, An Improved Upper Bound on the Queue Number of Planar Graphs (Algorithmica 2023, concluding discussion).
• Förster, Kaufmann, Merker, Pupyrev, and Raftopoulou, Linear Layouts of Bipartite Planar Graphs (GD 2023, Section 6).

Comments:

• A 2-degenerate bipartite planar graph requiring 3 queues is known.
• Every bipartite planar graph has a 28-queue layout.
• For 2-degenerate plane quadrangulations, the sharper interval is 3–5.

QUEUE NUMBER OF PLANAR 3-TREESESTIMATED DIFFICULTY: EASY

Problem. Determine the queue number of planar 3-trees; the value is 4 or 5.

Asked in:

• Alam, Bekos, Gronemann, Kaufmann, and Pupyrev, Queue Layouts of Planar 3-Trees (Algorithmica 2021, Section 4).
• Bekos, Gronemann, and Raftopoulou, An Improved Upper Bound on the Queue Number of Planar Graphs (Algorithmica 2023, Section 6).

Comments:

• Alam, Bekos, Gronemann, Kaufmann, and Pupyrev constructed planar 3-trees requiring 4 queues.
• The same work gives a 5-queue layout for every planar 3-tree.
• An improvement from 5 to 4 would directly provide an improved general planar upper bound.

QUEUE NUMBER OF K-TREESESTIMATED DIFFICULTY: HARD

Problem. Determine the queue number of k-trees as a function of k; in particular, is it bounded by a polynomial in k?

Asked in:

• West, Stack and Queue Layouts (REGS 2009, Question 2).
• Wiechert, On the Queue-Number of Graphs with Bounded Tree-Width (Electronic Journal of Combinatorics 2017, Section 5).

Comments:

• Equivalently, determine the queue number of graphs with treewidth at most k.
• The original boundedness proof gave a doubly exponential upper bound in k.
• Wiechert proved the current 2^k−1 upper bound and, for every k≥2, the k+1 lower bound.
• The queue number of 1-trees is 1, and the queue number of 2-trees is 3, exactly matching Wiechert’s upper bound.
• Pathwidth p gives queue number at most p.

QUEUE NUMBER OF HYPERCUBESESTIMATED DIFFICULTY: MEDIUM

The n-dimensional hypercube Q_n has vertex set {0,1}ⁿ, with two vertices adjacent if and only if their binary strings differ in exactly one coordinate.

Problem. Determine qn(Q_n). In particular, does there exist a constant c such that qn(Q_n)≥n−c log n for every sufficiently large n?

Asked in:

• Gregor, Škrekovski, and Vukašinović, Queue Layouts of Hypercubes (SIAM Journal on Discrete Mathematics 2012).

Comments:

• The best lower bound is qn(Q_n)≥(1/2−o(1))n.
• Gregor, Škrekovski, and Vukašinović constructed a layout with n−⌊log₂n⌋ queues. Thus a positive answer to the problem would imply qn(Q_n)=n−Θ(log n).
• Earlier milestones successively improved the elementary n−1 upper bound.
• The folded hypercube FQ_n is obtained from Q_n by joining each binary string to its complement. Geng, Hao, and Yang proved qn(FQ_n)≤2n−2, and Pai improved this to qn(FQ_n)≤n. These bounds concern a supergraph of Q_n and do not improve the best known upper bound for qn(Q_n).

SPARSE TWIN-WIDTH AND QUEUE NUMBERESTIMATED DIFFICULTY: HARD

A hereditary graph class has bounded sparse twin-width if it has bounded twin-width and, for some fixed t, no graph in the class contains K_t,t as a subgraph.

Problem. Does every hereditary graph class of bounded sparse twin-width have bounded queue number?

Asked in:

• Dujmović, Eppstein, Hickingbotham, Morin, and Wood, Stack-Number Is Not Bounded by Queue-Number (Combinatorica 2022, Section 3).
• Bonnet, Geniet, Tessera, and Thomassé, Twin-width VII: Groups (2022 preprint, Sections 1.4 and 8).

Comments:

• Every class with queue number at most q has twin-width at most 2^2O(q); consequently every hereditary class of bounded queue number has bounded sparse twin-width.
• A 2-lift replaces each vertex by two copies and each edge by one of the two perfect matchings between the corresponding pairs. Random iterated 2-lifts of K₄ yield cubic expanders, and every graph obtained from K₄ by iterated 2-lifts has twin-width at most 6. The queue numbers of these expanders are conjectured to be unbounded; proving this would give a negative answer after taking their hereditary closure.
• There is a hereditary graph class with queue number at most 4, and hence bounded sparse twin-width, but with unbounded stack number. Thus the analogous implication for stack number is false.

POLYNOMIAL EXPANSION AND QUEUE NUMBERESTIMATED DIFFICULTY: HARD

A depth-r shallow minor of a graph G is obtained from a subgraph of G by contracting pairwise vertex-disjoint connected subgraphs of radius at most r. A graph class 𝒢 has polynomial expansion if there is a polynomial p such that every depth-r shallow minor H of every G∈𝒢 has |E(H)|/|V(H)|≤p(r).

Problem. Does every graph class with polynomial expansion have bounded queue number?

Asked in:

• Dvořák, Huynh, Joret, Liu, and Wood, Notes on Graph Product Structure Theory, Section 8, Open Problem 34.
• Dujmović, Eppstein, Hickingbotham, Morin, and Wood, Stack-Number Is Not Bounded by Queue-Number (Combinatorica 2022, Section 3).

Comments:

• Bounded queue number implies bounded expansion, but bounded expansion alone is not sufficient.
• Proper minor-closed classes have polynomial expansion and bounded queue number.
• Many product-structured and beyond-planar classes with polynomial expansion have bounded queue number.
• The bounded-queue/unbounded-stack separation class has polynomial expansion, so the analogous stack implication is false.

QUEUE NUMBER VS STACK NUMBERESTIMATED DIFFICULTY: HARD

Problem. Does there exist a function f:ℕ→ℕ such that qn(G)≤f(sn(G)) for every graph G?

Asked in:

• Heath, Leighton, and Rosenberg, Comparing Queues and Stacks as Machines for Laying Out Graphs (1992).
• Heath and Rosenberg, Laying Out Graphs Using Queues (1992).
• Dujmović and Wood, New Results in Graph Layout, Technical Report TR-03-04 (2003).
• Dujmović and Wood, Tree-Partitions of k-Trees with Applications in Graph Layout (WG 2003), Section 6.
• Dujmović, Track Layouts of Graphs (Ph.D. thesis, 2003), Open Problem 1.2.
• Dujmović and Wood, Stacks, Queues and Tracks: Layouts of Graph Subdivisions (2005, Open Problem 2).
• West, Stack and Queue Layouts, Question 3.
• Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood, Planar Graphs Have Bounded Queue-Number (JACM 2020, Open Problems, item 2).
• Dujmović, Eppstein, Hickingbotham, Morin, and Wood, Stack-Number Is Not Bounded by Queue-Number (2022), introduction and the subsection “Is queue-number bounded by stack-number?”.
• Leung, Graphs with Queue Number Three and Unbounded Stack Number (2023 preprint), introduction.
• Katheder, Kaufmann, Pupyrev, and Ueckerdt, Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs (STACS 2025), Open Problem 1.

Comments:

• Every 1-stack graph has queue number at most 2; every 2-stack graph is planar and hence has bounded queue number.
• It is enough to solve the problem for bipartite 3-stack graphs or for bipartite graphs admitting a (1,1)-mixed layout.
• A possibly easier first question is whether cubic graphs admitting a (1,1)-mixed layout have bounded queue number. Wood's counting argument gives cubic graphs with unbounded queue number, but does not give such layouts.
• The reverse implication is false: bounded queue number can coexist with unbounded stack number. In particular, the strong products of three paths have queue number at most 4, maximum degree at most 26, and unbounded stack number.

STACK NUMBER OF 2-QUEUE GRAPHSESTIMATED DIFFICULTY: HARD

Problem. Is the stack number of graphs with queue number at most 2 unbounded?

Asked in:

• Leung, Graphs with Queue Number Three and Unbounded Stack Number (2023 preprint), Section 8, Problem 8.2.

Comments:

• Every 1-queue graph has stack number at most 2.
• Graphs of queue number at most 4 and unbounded stack number were constructed in 2022.
• Leung’s unpublished preprint claims that the upper endpoint is queue number 3; thus only 2 versus 3 remains.

CHARACTERIZATION OF MIXED LAYOUTSESTIMATED DIFFICULTY: MEDIUM

A t-twist consists of t pairwise crossing edges, and a t-rainbow consists of t pairwise nesting edges. There are two t-thick patterns, each with t² edges: a t-twist in which every edge is replaced by a t-rainbow, and a t-rainbow in which every edge is replaced by a t-twist.

Problem. Does there exist a function F such that every ordered graph containing neither t-thick pattern has mixed page number at most F(t), without any bound on its maximum degree?

Asked in:

• Haun, Merker, and Pupyrev, Forbidden Patterns in Mixed Linear Layouts (STACS 2025, Section 5).

Comments:

• For bounded-degree ordered graphs, bounded mixed page number is equivalent to bounded thick patterns.
• Explicit bounds are known for separated matchings and for arbitrary matchings.
• For every fixed page bound at least 2, there is no finite exact obstruction set in full generality.

MIXED PAGE NUMBER OF COMPLETE GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine mpn(K_n) for every n, or at least determine lim mpn(K_n)/n if the limit exists.

Asked in:

• West, Quack Number: Queue/Stack Decomposition (REGS 2010, Question 2).
• Alam, Bekos, Gronemann, Kaufmann, and Pupyrev, The Mixed Page Number of Graphs (Theoretical Computer Science 2022, concluding open problems).

Comments:

• ⌈3(n−4)/8⌉≤mpn(K_n)≤2⌈n/5⌉.
• The ordinary stack and queue numbers of K_n are both known exactly, so the gap is genuinely about mixing page types.

MIXED PAGE NUMBER OF COMPLETE BIPARTITE GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine mpn(K_n,n) when arbitrary vertex orders are permitted. (The separated variant is already known exactly.)

Asked in:

• West, Quack Number: Queue/Stack Decomposition (REGS 2010, Question 2).
• Alam, Bekos, Gronemann, Kaufmann, and Pupyrev, The Mixed Page Number of Graphs (Theoretical Computer Science 2022, concluding open problems).

Comments:

• For separated layouts the exact value is ⌈2n/3⌉.
• Without separation, ⌈n/3⌉≤mpn(K_n,n)≤⌊n/2⌋.
• The best known unrestricted layouts exploit interleaving, which is precisely what the separated theorem forbids.

MIXED PAGE NUMBER OF PLANAR GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine the mixed page number of planar graphs; the value is 3 or 4.

Discussed in:

• Pupyrev, Mixed Linear Layouts of Planar Graphs (GD 2017, concluding section).
• Alam, Bekos, Gronemann, Kaufmann, and Pupyrev, The Mixed Page Number of Graphs (Theoretical Computer Science 2022, concluding open problems).
• Angelini, Bekos, Kindermann, and Mchedlidze, On Mixed Linear Layouts of Series-Parallel Graphs (Theoretical Computer Science 2022, open-problems section).

Comments:

• The upper bound follows from the four-stack theorem for planar graphs. The lower bound can be obtained by taking the planar disjoint union of a graph with no 2-stack layout, a graph with no 2-queue layout, and a graph with no (1,1)-mixed layout; these exhaust the three possible types of two-page mixed layouts.
• It remains open whether every planar graph admits a (2,1)-mixed layout. More generally, no fixed pair s,q>0 with 2<s+q≤4 is known to suffice for all planar graphs.
• There are planar graphs with no (1,1)-mixed layout, even among 2-trees and among bipartite planar graphs. These examples do not establish mixed page number 3 because the same graphs may admit two-stack or two-queue layouts.

(1,2)-MIXED LAYOUTS OF 2-TREESESTIMATED DIFFICULTY: EASY

Problem. Does every 2-tree admit a (1,2)-mixed layout?

Asked in:

• Angelini, Bekos, Kindermann, and Mchedlidze, On Mixed Linear Layouts of Series-Parallel Graphs (Theoretical Computer Science 2022, open-problems section).

Comments:

• Every 2-tree has stack number at most 2 and queue number at most 3.
• Some 2-trees admit no (1,1)-mixed layout.

FOREST STACK NUMBER VS STACK NUMBERESTIMATED DIFFICULTY: HARD

Problem. Is fsn(G)≤sn(G)+1 for every graph G, where fsn denotes forest stack number?

Asked in:

• Dujmović and Wood, Graph Treewidth and Geometric Thickness Parameters (2007), Section 10, “Book Arboricity”.
• Scherzer, Forest Stack Layouts (bachelor’s thesis, 2022), Conjecture 1.1 and Question 5.4.

Comments:

• The density argument motivating the conjecture gives |E(G)|≤(sn(G)+1)(|V(G)|−1), but it does not construct forest pages.
• For every k, there exists a graph with stack number k and forest stack number k+1, so the proposed additive constant would be best possible.
• For complete graphs, fsn(K_n)=⌈n/2⌉; every outerplanar graph has forest stack number at most 2, every planar 3-tree at most 3, and every k-tree at most k+1.
• With a prescribed vertex order, the ratio between forest stack number and stack number can be at least 3/2, and a 2-stack order may require four forest stacks. There is also an upward-planar DAG D with sn(D)=2 and fsn(D)≥4.

FOREST STACK NUMBER OF COMPLETE BIPARTITE GRAPHSESTIMATED DIFFICULTY: EASY

Problem. Determine fsn(K_m,n) for all positive integers m,n; in particular, characterize the pairs for which fsn(K_m,n)<min{m,n}.

Asked in:

• Scherzer, Forest Stack Layouts (bachelor’s thesis, 2022), Questions 5.1–5.2 and the preceding discussion.

Comments:

• The star decomposition gives fsn(K_m,n)≤min{m,n}.
• If m≤n and n>m²−m+1, then fsn(K_m,n)=m.
• The first strict example is fsn(K_4,4)=3<4.
• Forest-page density gives fsn(K_m,n)≥⌈mn/(m+n−1)⌉.
• Even ordinary sn(K_n,n) is known only between ⌈n/2⌉ and ⌊2n/3⌋+1.

UNION STACK NUMBER OF COMPLETE GRAPHSESTIMATED DIFFICULTY: EASY

Problem. Determine sn_u(K_n) for every n, or at least determine its asymptotic leading constant.

Asked in:

• Merker, Ordered Covering Numbers, Question 5.1 (master’s thesis, 2020).
• Felsner, Merker, Ueckerdt, and Valtr, Linear Layouts of Complete Graphs (GD 2021, Section 5, Question 9).

Comments:

• n/3−O(1)≤sn_u(K_n)≤4n/9+O(1).
• The local stack number is known up to an additive constant: n/3±O(1).
• For n≥4, the classical stack number is exactly ⌈n/2⌉.
• Among the four local/union stack/queue complete-graph variants in the source, this is the remaining asymptotic gap.

LOCAL AND UNION LAYOUTS OF COMPLETE BIPARTITE GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine the local and union stack and queue numbers of K_m,n, exactly or asymptotically, both with arbitrary orders and with the two partite sets separated.

Related to:

• Felsner, Merker, Ueckerdt, and Valtr, Linear Layouts of Complete Graphs (GD 2021, conclusion).

Comments:

• Local and union stack number differ by at most a constant factor in general, while ordinary stack number is not bounded by either parameter.
• Three of the four corresponding local/union stack/queue parameters of complete graphs are known up to an additive constant.
• Even the ordinary stack number of complete bipartite graphs is not known exactly in general.

LOCAL AND UNION STACK NUMBERS OF PLANAR GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine the local and union stack numbers of planar graphs; each value is 3 or 4.

Asked in:

• Merker, Local Page Numbers (bachelor’s thesis, 2018), Questions 6.1–6.2.
• Merker and Ueckerdt, Local and Union Page Numbers (GD 2019), Section 5.

Comments:

• Every planar graph has local and union stack number at most 4. A planar graph with local stack number 3 is known; since local stack number never exceeds union stack number, both class maxima are at least 3.
• The classical four-stack planar witnesses do not automatically require four local or union stacks.

LOCAL STACK NUMBER OF K-TREESESTIMATED DIFFICULTY: MEDIUM

Problem. For every integer k≥3, determine the local stack number of graphs with treewidth at most k; the value is k or k+1.

Asked in:

• Merker, Local Page Numbers (bachelor’s thesis, 2018), Question 6.4.
• Merker and Ueckerdt, Local and Union Page Numbers (GD 2019), Sections 4–5.

Comments:

• Every k-tree has local stack number at most k+1.
• For every k≥3, a k-tree with local stack number k is known.
• The classical maximum stack number is k+1 for every k≥3, but that construction need not force the local maximum.

LOCAL QUEUE NUMBER OF PLANAR GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine the local queue number of planar graphs; the value is 3 or 4.

Asked in:

• Merker and Ueckerdt, The Local Queue Number of Graphs with Bounded Treewidth (GD 2020, Question 13).

Comments:

• Every planar graph has local queue number at most 4.
• A planar treewidth-2 construction has local queue number 3.
• Ordinary planar queue number is at least 4, but that lower bound does not transfer to the local relaxation.

LOCAL QUEUE NUMBER OF K-TREESESTIMATED DIFFICULTY: MEDIUM

Problem. For every integer k≥2, determine the local queue number of graphs with treewidth at most k; the value lies between ⌈k/2⌉+1 and k+1.

Asked in:

• Merker and Ueckerdt, The Local Queue Number of Graphs with Bounded Treewidth (GD 2020, Question 12).

Comments:

• For k=1, the maximum local queue number is 1.
• The upper and lower bounds are due to Merker and Ueckerdt.
• The local queue number of graphs with treewidth at most 2 is 3.
• Union queue number is linear on k-trees, but this does not fix the local value.

DISPERSABLE BOOK THICKNESS OF PLANAR BIPARTITE GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Is every planar bipartite graph G dispersable; equivalently, does dbt(G)=Δ(G)?

Asked in:

• Alam, Bekos, Dujmović, Gronemann, Kaufmann, and Pupyrev, On Dispersable Book Embeddings (Theoretical Computer Science 2021, conclusion).
• Kainen and Overbay, Cubic Planar Bipartite Graphs Are Dispersable (2021 preprint, Section 4).

Comments:

• Trees, even cycles, and complete bipartite graphs are dispersable.
• Every cubic planar bipartite graph is dispersable.
• Every planar bipartite graph G satisfies dbt(G)≤4Δ(G), since dbt(G)≤sn(G)Δ(G) and every planar graph has stack number at most 4.
• Planarity is essential: for every fixed integer k≥3, there are k-regular bipartite graphs with arbitrarily large dispersable book thickness.

DISPERSABLE BOOK THICKNESS OF VERTEX-TRANSITIVE GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Prove or disprove that every bipartite vertex-transitive graph G satisfies dbt(G)=Δ(G) and every nonbipartite vertex-transitive graph satisfies dbt(G)=Δ(G)+1.

Asked in:

• Alam, Bekos, Dujmović, Gronemann, Kaufmann, and Pupyrev, On Dispersable Book Embeddings (Theoretical Computer Science 2021).
• Kainen and Overbay, Cubic Planar Bipartite Graphs Are Dispersable (2021 preprint, conclusion).
• Kainen, Joslin, and Overbay, On Dispersability of Some Circulant Graphs (JGAA 2024, Section 8).
• Overbay, Joslin, and Kainen, All Bipartite Circulants Are Dispersable (The Art of Discrete and Applied Mathematics 2025, introduction).

Comments:

• Every bipartite circulant graph is dispersable.
• Regularity without vertex transitivity is insufficient: for every fixed degree at least 3 there are regular bipartite graphs of arbitrarily large dispersable book thickness.
• The Gray graph and Folkman graph are concrete non-vertex-transitive counterexamples to the older regular-bipartite conjecture.

TRACK NUMBER OF PLANAR GRAPHSESTIMATED DIFFICULTY: HARD

Problem. Determine the track number of planar graphs; the value lies between 8 and 225.

Asked in:

• Dujmović, Pór, and Wood, Track Layouts of Graphs (2004), Section 7.
• Dujmović, Morin, and Wood, Layout of Graphs with Bounded Tree-Width (2005, Section 8, Open Problems 1–2).
• Dujmović and Wood, Three-Dimensional Drawings (2013), Open Problem 14.2.
• Pupyrev, Improved Bounds for Track Numbers of Planar Graphs (2020), Section 6 and the planar row of Table 1.

Comments:

• Bounded planar queue number implies bounded planar track number.
• Pupyrev gave the explicit upper bound 225 and constructed a planar graph requiring 8 tracks.
• The earlier general conversion through queue layouts produced a vastly larger constant.
• Outerplanar graphs have exact maximum track number 5.

TRACK NUMBER OF PLANAR 3-TREESESTIMATED DIFFICULTY: EASY

Problem. Determine the track number of planar 3-trees; the value lies between 8 and 25.

Asked in:

• Pupyrev, Improved Bounds for Track Numbers of Planar Graphs (2020), Section 6 and the planar-3-tree row of Table 1.

Comments:

• A planar 3-tree requiring 8 tracks is known.
• Every planar 3-tree has a 25-track layout; the previous upper bound was 4,000.
• The lower-bound transfer adds three tracks to an outerplanar witness, whose exact maximum is 5.

TRACK NUMBER OF K-TREESESTIMATED DIFFICULTY: HARD

Problem. Determine the track number of graphs with treewidth at most k as a function of k; in particular, is it polynomial in k, or at most 2^O(k)?

Asked in:

• Wiechert, On the Queue-Number of Graphs with Bounded Tree-Width (2017, Section 5).
• Pupyrev, Improved Bounds for Track Numbers of Planar Graphs (2020), Section 6, Open Problem 1.

Comments:

• The best general upper bound is (k+1)(2^k+1−2)^k=2^Θ(k2).
• The lower bound is quadratic in k.
• At treewidth 2, the interval is 7–15.
• Planar 3-trees have the much smaller special upper bound 25.

TRACK NUMBER VS QUEUE NUMBERESTIMATED DIFFICULTY: HARD

For every integer q≥1, let T(q):=sup{tn(G):qn(G)≤q}.

Problem. Determine T(q) as a function of q.

Asked in:

• Pupyrev, Improved Bounds for Track Numbers of Planar Graphs (2020), Section 6, Open Problem 2.

Comments:

• Every t-track graph has queue number at most t−1, and this direction is tight.
• The general reverse conversion gives T(q)≤4q·4^{q(2q−1)(4q−1)}.
• Every 1-queue graph has a 4-track layout.
• If G has queue number at most q and acyclic chromatic number at most c, then tn(G)≤c(2q)^c−1.

STACK NUMBER OF UPWARD-PLANAR DAGSESTIMATED DIFFICULTY: HARD

Problem. Does there exist a constant c such that every upward-planar DAG G has upward stack number at most c?

Discussed in:

• Nowakowski and Parker, Ordered Sets, Pagenumbers and Planarity (Order 1989, concluding questions).
• Heath and Pemmaraju, Stack and Queue Layouts of Posets (SIAM Journal on Discrete Mathematics 1997, introduction and Section 7).
• Frati, Fulek, and Ruiz-Vargas, On the Page Number of Upward Planar Directed Acyclic Graphs (Journal of Graph Algorithms and Applications 2013, introduction).
• Binucci, Da Lozzo, Di Giacomo, Didimo, Mchedlidze, and Patrignani, Upward Book Embeddability of st-Graphs: Complexity and Algorithms (Algorithmica 2023, introduction).
• Bhore, Da Lozzo, Montecchiani, and Nöllenburg, On the Upward Book Thickness Problem: Combinatorial and Complexity Results (European Journal of Combinatorics 2023, introduction).
• Nöllenburg and Pupyrev, On Families of Planar DAGs with Constant Stack Number (GD 2023), Introduction, Open Problem 1.
• Jungeblut, Merker, and Ueckerdt, A Sublinear Bound on the Page Number of Upward Planar Graphs (SIAM Journal on Discrete Mathematics 2023, abstract and introduction).
• Jungeblut, Merker, and Ueckerdt, Directed Acyclic Outerplanar Graphs Have Constant Stack Number (TheoretiCS 2025, Open Problems 1.2 and 5.3).

Comments:

• The general upper bound is O((n log n)^2/3).
• An upward-planar graph requiring 5 pages is known.
• Outerplanar DAGs have a constant upper bound, currently 1,160.
• Every upward-planar embedding containing no embedded copy of the directed graph N with arcs (a,b), (c,b), and (c,d) admits an embedding-preserving upward 2-stack layout; this class includes series-parallel families.
• Upward-planar 3-trees form another bounded subclass.

MIXED PAGE NUMBER OF UPWARD-PLANAR DAGSESTIMATED DIFFICULTY: HARD

Problem. Does there exist a constant c such that mpn(G)≤c for every upward-planar DAG G?

Asked in:

• Haun, Mixed Page Number of Planar Directed Acyclic Graphs (bachelor’s thesis, 2023), Open Question 6.3.
• Haun, Merker, and Pupyrev, Forbidden Patterns in Mixed Linear Layouts (STACS 2025, conclusion).

Comments:

• There is an upward-planar DAG with mixed page number at least 3; this lower bound already holds for upward-planar bipartite DAGs.
• Upward-planar DAGs have unbounded queue number: upward-planar Hasse diagrams of n-element planar posets can require Ω(√n) queues. Thus any constant mixed bound must genuinely use stack pages.
• If G=(A∪B,E) is upward-planar and bipartite and every arc is directed from A to B, then sn(G), qn(G), and mpn(G) are at most 56. Boundedness remains open for general upward-planar bipartite DAGs.
• Upward planarity is essential: directed acyclic 2-trees can have unbounded mixed page number. Even for bounded-degree upward-planar DAGs the problem remains open; it would suffice to find topological orders excluding a fixed-size thick pattern.

STACK NUMBER OF PLANAR POSETSESTIMATED DIFFICULTY: HARD

Problem. Does there exist a constant c such that every planar poset has stack number at most c?

Discussed in:

• Nowakowski and Parker, Ordered Sets, Pagenumbers and Planarity (Order 1989, concluding questions).
• Heath and Pemmaraju, Stack and Queue Layouts of Posets (SIAM Journal on Discrete Mathematics 1997, introduction and Section 7).
• Frati, Fulek, and Ruiz-Vargas, On the Page Number of Upward Planar Directed Acyclic Graphs (Journal of Graph Algorithms and Applications 2013, introduction).
• Binucci, Da Lozzo, Di Giacomo, Didimo, Mchedlidze, and Patrignani, Upward Book Embeddability of st-Graphs: Complexity and Algorithms (Algorithmica 2023, introduction).
• Bhore, Da Lozzo, Montecchiani, and Nöllenburg, On the Upward Book Thickness Problem: Combinatorial and Complexity Results (European Journal of Combinatorics 2023, introduction).
• Nöllenburg and Pupyrev, On Families of Planar DAGs with Constant Stack Number (GD 2023), introduction.
• Jungeblut, Merker, and Ueckerdt, A Sublinear Bound on the Page Number of Upward Planar Graphs (SIAM Journal on Discrete Mathematics 2023, introduction).
• Jungeblut, Merker, and Ueckerdt, Directed Acyclic Outerplanar Graphs Have Constant Stack Number (TheoretiCS 2025, Section 1.1).

Comments:

• The best lower bound is 5.
• The sublinear upper bound for upward-planar DAGs applies.
• N-free ordered families, whose posets contain no four-element N-shaped subposet, including series-parallel orders, use at most 2 pages.

STACK NUMBER OF UPWARD-PLANAR 2-TREESESTIMATED DIFFICULTY: MEDIUM

Problem. Does there exist a constant c such that every upward-planar directed acyclic 2-tree has upward stack number at most c?

Asked in:

• Jungeblut, Merker, and Ueckerdt, Directed Acyclic Outerplanar Graphs Have Constant Stack Number (TheoretiCS 2025, Open Problem 5.2).

Comments:

• Outerplanar DAGs have upward stack number at most 1,160; hence boundedness holds for upward-planar directed acyclic 2-trees whose underlying graphs are outerplanar.
• Without upward planarity, directed acyclic 2-trees have unbounded stack number.
• Upward-planar 3-trees have bounded stack number, but an upward-planar completion argument does not cover partial 3-trees.
• For n-vertex upward-planar DAGs, the known class maximum is at least 5 and at most O((n log n)^2/3).

STACK NUMBER OF OUTERPLANAR DAGSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine the upward stack number of outerplanar DAGs; the value lies between 4 and 1,160.

Asked in:

• Pemmaraju, Exploring the Powers of Stacks and Queues via Graph Layouts (doctoral thesis, 1992, Chapter 4).
• Heath, Pemmaraju, and Trenk, Stack and Queue Layouts of Directed Acyclic Graphs: Part I (1999, Conjecture 1.1).
• Bhore, Da Lozzo, Montecchiani, and Nöllenburg, On the Upward Book Thickness Problem: Combinatorial and Complexity Results (European Journal of Combinatorics 2023, Section 5, question (i)).
• Nöllenburg and Pupyrev, On Families of Planar DAGs with Constant Stack Number (GD 2023, conclusion).
• Jungeblut, Merker, and Ueckerdt, Directed Acyclic Outerplanar Graphs Have Constant Stack Number (TheoretiCS 2025, Section 5, Open Problem 5.1).
• Alam, Bekos, Gronemann, and Kaufmann, The Page Number of Monotone Directed Acyclic Outerplanar Graphs Is Four or Five (GD 2025), introduction and Section 5.

Comments:

• An outerplanar DAG requiring 4 pages is known.
• The first constant upper bound was 24,776.
• The analysis of monotone outerplanar DAGs reduced the general bound to 1,160 in 2025.

QUEUE NUMBER OF PLANAR POSETSESTIMATED DIFFICULTY: MEDIUM

Problem. Is the queue number of n-element planar posets Θ(√n)?

Asked in:

• Heath and Pemmaraju, Stack and Queue Layouts of Posets (SIAM Journal on Discrete Mathematics 1997, Section 7).
• Knauer, Micek, and Ueckerdt, The Queue-Number of Posets of Bounded Width or Height (GD 2018, conclusion, Conjecture 4).
• Felsner, Ueckerdt, and Wille, On the Queue-Number of Partial Orders (GD 2021, conclusion).
• Goubault-Larrecq, Queue Number of Planar Posets, Section 4.3, Conjectures 3–4 (M1 report).

Comments:

• There are planar posets with queue number Ω(√n).
• Every planar poset of width w has queue number at most 3w−2.
• The width-dependent bound does not give the conjectured O(√n) bound for arbitrary planar posets.

QUEUE NUMBER VS WIDTH FOR PLANAR POSETSESTIMATED DIFFICULTY: MEDIUM

Problem. Is qn(P)≤width(P) for every planar poset P?

Asked in:

• Felsner, Ueckerdt, and Wille, On the Queue-Number of Partial Orders (GD 2021), introduction and Section 4.
• Alam, Bekos, Gronemann, Kaufmann, and Pupyrev, Lazy Queue Layouts of Posets (Algorithmica 2023, Section 6, Conjecture 2).

Comments:

• The current interval for the class maximum is w to 3w−2.
• The conjectured w bound holds when there is both a unique minimum and a unique maximum.
• It also holds at width 2.
• Quadratic lower-bound constructions for general posets are nonplanar.

QUEUE NUMBER OF TWO-DIMENSIONAL POSETSESTIMATED DIFFICULTY: EASY

Problem. Does the queue number of posets with dimension at most 2 and width at most w grow as o(w²)?

Asked in:

• Pupyrev, Queue Layouts of Two-Dimensional Posets (GD 2022, Section 4, first concluding question).

Comments:

• The current lower bound is 2(w−1).
• The current upper bound is w(w+1)/2.
• The lower-bound construction disproves qn(P)≤width(P), even for posets P of dimension 2.
• The quadratic lower bound for unrestricted posets does not have dimension 2.

RIQUE NUMBER OF COMPLETE GRAPHSESTIMATED DIFFICULTY: EASY

Problem. Prove or disprove that riq(K_n)=⌊(n−1)/3⌋ for every n≥4.

Asked in:

• Bekos, Felsner, Kindermann, Kobourov, Kratochvíl, and Rutter, The Rique-Number of Graphs (GD 2022, Section 6, item (ii)).
• Bekos, Kaufmann, Pavlidi, and Rieger, On the Deque and Rique Numbers of Complete and Complete Bipartite Graphs (CCCG 2023, concluding discussion).

Comments:

• For n≥4, (1−1/√2)(n−2)≤riq(K_n)≤⌊(n−1)/3⌋.
• The conjectured exact value has been verified computationally for 4≤n≤30.
• For comparison, deque-number(K_n)=⌈n/4⌉; the one-sided input restriction prevents transferring this formula to riques.

RIQUE NUMBER OF PLANAR GRAPHSESTIMATED DIFFICULTY: EASY

Problem. Is riq(G)≤2 for every planar graph G?

Asked in:

• Bekos, Felsner, Kindermann, Kobourov, Kratochvíl, and Rutter, The Rique-Number of Graphs (GD 2022, Section 6, item (iv)).
• Bekos, Kaufmann, Pavlidi, and Rieger, On the Deque and Rique Numbers of Complete and Complete Bipartite Graphs (CCCG 2023, Section 6, item (ii)).
• Kaufmann and Pavlidi, A Note on Mixed Linear Layouts of Planar Graphs, introduction and conclusion (EuroCG 2024).

Comments:

• The maximum value of riq(G) over planar graphs G is between 2 and 4.
• One-rique graphs are precisely the planar strongly one-sided subhamiltonian graphs; recognizing maximal planar one-rique graphs takes O(n²) time.
• Every series-parallel graph and every planar bipartite graph G satisfies riq(G)≤2, and both class bounds are tight.

PRIORITY-QUEUE NUMBER OF COMPLETE GRAPHSESTIMATED DIFFICULTY: EASY

Problem. Determine pqn(K_n).

Asked in:

• Di Giacomo, Didimo, Förster, Ueckerdt, and Zink, Linear Layouts of Graphs with Priority Queues (WADS 2025, Section 7, item (i)).

Comments:

• The established bounds are ⌊(3−√5)n/8⌋≤pqn(K_n)≤n−1.
• For comparison, ⌈(3−√5)n/4⌉≤pqn(K_n,n)≤n.

PRIORITY-QUEUE NUMBER OF OUTERPLANAR GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Do outerplanar graphs have bounded priority-queue number?

Asked in:

• Di Giacomo, Didimo, Förster, Ueckerdt, and Zink, Linear Layouts of Graphs with Priority Queues (WADS 2025, Section 7, item (iii)).

Comments:

• Every tree has priority-queue number 1.
• Every graph of pathwidth at most p has priority-queue number at most p+1.
• Priority-queue number is unbounded for graphs of treewidth 2, but this does not settle the outerplanar case.

DENSITY OF PRIORITY-QUEUE GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Does there exist a function f such that |E(G)|≤f(k)|V(G)| for every graph G with pqn(G)≤k?

Asked in:

• Di Giacomo, Didimo, Förster, Ueckerdt, and Zink, Linear Layouts of Graphs with Priority Queues (WADS 2025, Section 7, item (iv)).

Comments:

• Graphs with priority-queue number 1 form a minor-closed class characterized by eight forbidden minors.
• Complete and balanced complete bipartite graphs have priority-queue number Θ(n); consequently, any bound of the form f(k)|V(G)| must have f(k)=Ω(k).

2-QUEUE GRAPH RECOGNITIONESTIMATED DIFFICULTY: EASY

Problem. Given a graph G, determine whether qn(G)≤2. Determine the computational complexity of this decision problem.

Discussed in:

• Heath and Rosenberg, Laying Out Graphs Using Queues (1992).
• Depian, Fink, Ganian, and Surianarayanan, Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms (ESA 2025).

Comments:

• Recognizing graphs with queue number at most 1 is NP-complete. This does not imply hardness for queue number at most 2.
• When the vertex order is prescribed, the minimum number of queues equals the size of a largest rainbow and an optimal queue assignment is computable in polynomial time.
• The 2019 thesis proposes the reduction G↦K₂∨G, where two adjacent vertices are added and made adjacent to every vertex of G, but the corresponding peer-reviewed paper omits the two-queue claim.
• Minimum queue layout is fixed-parameter tractable when parameterized by vertex integrity.

(1,1)-MIXED LAYOUT RECOGNITIONESTIMATED DIFFICULTY: EASY

Problem. Given a graph G, determine whether G admits a (1,1)-mixed layout. Determine the computational complexity both in general and when G is restricted to be a 2-tree or a bipartite planar graph.

Asked in:

• Klute, Avoiding Crossings in Non-Planar Graph Layouts, Open Problem 3 (doctoral dissertation, 2020).
• Angelini, Bekos, Kindermann, and Mchedlidze, On Mixed Linear Layouts of Series-Parallel Graphs (Theoretical Computer Science 2022, open-problems section).
• Förster, Kaufmann, Merker, Pupyrev, and Raftopoulou, Linear Layouts of Bipartite Planar Graphs (WADS 2023, Section 6).

Comments:

• The problem is in NP. With a fixed vertex order, deciding whether the edges can be partitioned into one stack and one queue reduces to 2-SAT.
• Minimizing the number of mixed pages for a fixed vertex order is NP-hard, even for matchings, when the page bound is part of the input.
• Recognizing 1-stack graphs is linear-time solvable, whereas recognizing 1-queue graphs is NP-complete; neither result determines the complexity of the larger (1,1)-mixed-layout class.
• There exist 2-trees and bipartite planar graphs with no (1,1)-mixed layout, but recognition remains open on both classes.
• Recognizing (2,1)-mixed layouts is NP-complete; this does not settle the (1,1)-mixed-layout case.

ONE-RIQUE RECOGNITIONESTIMATED DIFFICULTY: EASY

A graph is strongly one-sided subhamiltonian if it is a subgraph of a planar graph having an embedding with a Hamiltonian path v₁,…,v_n such that every non-path edge v_iv_j with 1<i<j leaves v_i on the same side of the path.

Problem. Determine the computational complexity of deciding whether riq(G)≤1 for a graph G.

Asked in:

• Bekos, Felsner, Kindermann, Kobourov, Kratochvíl, and Rutter, The Rique-Number of Graphs (GD 2022, Section 6, item (i)).

Comments:

• A graph G satisfies riq(G)=1 if and only if it is planar strongly one-sided subhamiltonian.
• For a fixed plane embedding, strong one-sided Hamiltonicity is testable in O(n²) time.
• For maximal planar graphs, riq(G)≤1 is recognizable in O(n²) time.

PRIORITY-QUEUE LAYOUT RECOGNITIONESTIMATED DIFFICULTY: MEDIUM

Problem. For every fixed integer k>1, determine the complexity of deciding whether pqn(G)≤k. For an edge-weighted graph ⟨G,w⟩, determine the complexity of deciding whether pqn(G,w)≤k when k is fixed or when the vertex order is not prescribed.

Asked in:

• Di Giacomo, Didimo, Förster, Ueckerdt, and Zink, Linear Layouts of Graphs with Priority Queues (WADS 2025, concluding section).

Comments:

• Graphs satisfying pqn(G)=1 have an eight-forbidden-minor characterization and are recognizable in linear time.
• This universal characterization does not decide whether an arbitrary edge-weighted graph satisfies pqn(G,w)=1; for example, pqn(G,w)=1 for every graph when all edge weights are equal.
• With a prescribed vertex order, deciding whether pqn(G,w)≤k is NP-complete when k is part of the input.
• Priority-queue number is bounded by pathwidth but is unbounded already at treewidth 2.

DEFECTIVE QUEUE LAYOUT RECOGNITIONESTIMATED DIFFICULTY: MEDIUM

Problem. For fixed integers d,h≥1, determine the complexity of deciding whether a graph admits a d-defective h-queue layout.

Asked in:

• Bekos, Binucci, Di Giacomo, Didimo, Grilli, Pavlidi, Tappini, and Weinberger, Defective Linear Layouts of Graphs (Poster Abstract), Section 4, item (i) (GD 2025).

Comments:

• Every n-vertex graph with a d-defective h-queue layout satisfies an explicit linear edge bound.
• The d-defective queue number of K_n has explicit lower and upper bounds, which coincide when d=1.
• Outer 1-planar graphs—graphs with a 1-planar drawing in which every vertex is incident with the outer face—have 1-defective queue number 2; planar graphs have 1-defective queue number at most 33.

DISPERSABLE BOOK EMBEDDING RECOGNITIONESTIMATED DIFFICULTY: MEDIUM

Problem. Determine the complexity of deciding dbt(G)≤k and of deciding whether dbt(G)=Δ(G). Determine whether these problems are FPT by k+tw(G), vertex-cover number, or feedback-edge number.

Related to:

• Alam, Bekos, Dujmović, Gronemann, Kaufmann, and Pupyrev, On Dispersable Book Embeddings (Theoretical Computer Science 2021).
• Bhore, Ganian, Montecchiani, and Nöllenburg, Parameterized Algorithms for Book Embedding Problems (JGAA 2020).

Comments:

• General regular bipartite graphs need not be dispersable, even at every fixed degree at least 3.
• Every cubic bipartite planar graph is dispersable.
• Many special graph families have been classified, but no general recognition or parameterized-complexity classification is known.

PARAMETERIZED STACK NUMBERESTIMATED DIFFICULTY: HARD

Problem. Is the decision problem “sn(G)≤k?” fixed-parameter tractable parameterized by k+tw(G), or by k+td(G)?

Asked in:

• Ganian, Open Problem Session at GROW 2019, Problem Set 7, Questions 7.1–7.3.
• Bhore, Ganian, Montecchiani, and Nöllenburg, Parameterized Algorithms for Book Embedding Problems (JGAA 2020, conclusion).
• Ganian, Montecchiani, Nöllenburg, and Zehavi, Parameterized Complexity in Graph Drawing, Section 4.4.
• Depian, Fink, Ganian, and Surianarayanan, Linear Layouts Revisited (ESA 2025, Section 6).

Comments:

• The problems are FPT by vertex-cover number, and more recently by vertex integrity.
• The 2-page case has a single-exponential treewidth algorithm.
• Minimum-page book embedding is FPT by feedback-edge number, the minimum number of edges whose deletion leaves a forest.
• Every graph of treewidth at most t has stack number at most t+1, and this bound is tight for every t≥3; these structural bounds do not supply the general recognition algorithm.

PARAMETERIZED QUEUE NUMBERESTIMATED DIFFICULTY: MEDIUM

Problem. Is the decision problem “qn(G)≤k?” fixed-parameter tractable parameterized by k+tw(G), or by k+td(G)?

Asked in:

• Bhore, Ganian, Montecchiani, and Nöllenburg, Parameterized Algorithms for Queue Layouts (JGAA 2022, conclusion, Questions 1–2).
• Ganian, Montecchiani, Nöllenburg, and Zehavi, Parameterized Complexity in Graph Drawing, Section 4.4.
• Ordyniak, The Parameterized Complexity of Queue Number Using Structural Parameters, Section 4.8.
• Depian, Fink, Ganian, and Surianarayanan, Linear Layouts Revisited (ESA 2025, Section 6).

Comments:

• Minimum queue layout is FPT by vertex integrity.
• Bounded page width and a bounded number of queues yield an XP algorithm.
• The special case of one queue is fixed-parameter tractable when parameterized by treedepth.
• Treewidth gives an exponential combinatorial bound on queue number, but not the desired parameterized recognition algorithm.

EXACT ALGORITHMS FOR CLASSICAL LAYOUTSESTIMATED DIFFICULTY: MEDIUM

Problem. Do algorithms with running time 2^O(n) exist for computing sn(G) and qn(G) on an n-vertex graph G?

Asked in:

• Depian, Fink, Ganian, and Surianarayanan, Linear Layouts Revisited (ESA 2025, Section 6).

Comments:

• One-page queue layout has a 2^O(n)-time algorithm.
• Two-page book embedding has a tight 2^O(√n)-time algorithm under the Exponential Time Hypothesis (ETH).
• For arbitrary page counts, the general 2025 method does not yield a 2^O(n)-time algorithm.

PARAMETERIZED STACK LAYOUT EXTENSIONESTIMATED DIFFICULTY: MEDIUM

Problem. A Stack Layout Extension instance consists of a graph G, a subgraph H with a prescribed ℓ-stack layout, and asks whether both the vertex order and page assignment extend to all of G. Let κ:=|V(G)∖V(H)|+|E(G)∖E(H)|. Is this problem fixed-parameter tractable parameterized by κ+ℓ?

Asked in:

• Depian, Fink, Ganian, and Nöllenburg, The Parameterized Complexity of Extending Stack Layouts (JGAA 2026, Section 9).

Comments:

• The problem is FPT when only edges are missing.
• It is para-NP-hard parameterized by vertex-plus-edge deletion distance—the minimum number of vertex and edge deletions needed to obtain H from G—already when H is obtained by deleting two vertices.
• An FPT algorithm is known for κ plus page width plus ℓ.
• For κ+ℓ, FPT is known when the missing vertices form an independent set.

QUEUE LAYOUT EXTENSIONESTIMATED DIFFICULTY: MEDIUM

Problem. Given a graph G, a partial vertex order, and a partial assignment of edges to ℓ queues, determine whether these partial choices extend to an ℓ-queue layout of G; classify the classical and parameterized complexity of this decision problem.

Asked in:

• Depian, Fink, Ganian, and Nöllenburg, The Parameterized Complexity of Extending Stack Layouts (JGAA 2026, Section 9).
• Depian, Fink, Ganian, and Nöllenburg, The Peculiarities of Extending Queue Layouts (WG 2025, Section 7).

Comments:

• Ordinary Queue Layout Extension from a completely laid-out subgraph is already studied: it has NP-complete, W[1]-hard, XP, and FPT regions, and is FPT parameterized by the number of missing vertices and edges plus the number of queues.
• The analogous stack-extension problem has para-NP-hard, W[1]-hard, XP, and FPT regions.
• The nesting constraint in queues changes the conflict structure, so the stack algorithms do not transfer directly.

PARAMETERIZED MIXED LAYOUTSESTIMATED DIFFICULTY: MEDIUM

Problem. For fixed s,q≥1, determine whether recognizing graphs with an (s,q)-mixed layout is FPT parameterized by vertex-cover number, treedepth, or treewidth. If s+q is variable, include it in the parameter.

Asked in:

• Bhore, Ganian, Montecchiani, and Nöllenburg, Parameterized Algorithms for Queue Layouts (JGAA 2022, conclusion, item 3).

Comments:

• Queue layout is FPT by vertex-cover number, and one-queue layout is FPT by treedepth.
• Several mixed recognition variants are NP-complete, but no comparable structural parameterized classification is known.
• For a fixed vertex order, feasibility of one stack and one queue is polynomial by 2-SAT.

KERNELIZATION FOR UPWARD BOOK THICKNESSESTIMATED DIFFICULTY: MEDIUM

Problem. Does Upward Book Thickness parameterized by vertex-cover number admit a polynomial kernel? Which parameters larger than domination number yield FPT algorithms, possibly including parameters smaller than vertex-cover number?

Asked in:

• Bhore, Da Lozzo, Montecchiani, and Nöllenburg, On the Upward Book Thickness Problem: Combinatorial and Complexity Results (European Journal of Combinatorics 2023, conclusion).

Comments:

• The problem is FPT by vertex-cover number through a kernel of size k^O(τ), where k is the page bound and τ is the vertex-cover number.
• The known kernel is not polynomial in the combined parameter.
• For every fixed k≥5, the problem remains NP-hard when domination number is O(k).

APPROXIMATION OF LAYOUT NUMBERSESTIMATED DIFFICULTY: HARD

For stack number, queue number, and mixed page number, the optimization objective is to minimize the number of pages over all vertex orders and edge-to-page assignments. A ρ-approximation outputs a valid stack, queue, or mixed layout, respectively, using at most ρ times the optimal number of pages.

Problem. Do these three optimization problems admit polynomial-time constant-factor approximation algorithms? Determine the best polynomial-time approximation ratio for each as a function of |V(G)|.

Related to:

• Heath and Rosenberg, Laying Out Graphs Using Queues (SIAM Journal on Computing 1992).
• de Col, Klute, and Nöllenburg, Mixed Linear Layouts: Complexity, Heuristics, and Experiments (GD 2019).
• Agrawal, Cabello, Kaufmann, Saurabh, Sharma, Uno, and Wolff, Eliminating Crossings in Ordered Graphs (SWAT 2024).

Comments:

• Unless P=NP, no polynomial-time approximation ratio smaller than 3/2 is possible for stack number, and none smaller than 2 is possible for queue number.
• When the vertex order is fixed, stack number has a polynomial-time O(log |V(G)|)-approximation and a 2^|E(G)||V(G)|^O(1)-time exact algorithm.
• When the vertex order is fixed, the minimum number of queues equals the size of a largest rainbow and is computable exactly in polynomial time.
• For a prescribed page budget, mixed-layout heuristics study the related but different objective of minimizing conflicts; they provide no approximation guarantee for minimum mixed page number.

DYNAMIC LAYOUTSESTIMATED DIFFICULTY: HARD

Problem. Under vertex and edge insertions or deletions, maintain a bounded-page stack, queue, or mixed layout while minimizing recourse, defined as the number of moved vertices and reassigned edges. Determine worst-case and amortized recourse bounds and competitive ratios against the best offline layout sequence.

Comments:

• Dynamic graph visualization has been studied extensively, with stability and preservation of the viewer’s mental map as primary objectives; planar graph stories provide a related model in which vertex positions remain fixed while the crossing-free visible edge set changes.

3-COLORING CIRCLE GRAPHSESTIMATED DIFFICULTY: HARD

Problem. Given a graph G and a linear order ≺ of V(G), let X(G,≺) be the graph whose vertices are E(G), with two independent edges adjacent exactly when their endpoints alternate in ≺. Determine the computational complexity of deciding whether χ(X(G,≺))≤3; equivalently, determine the complexity of Fixed-Order 3-Stack Layout.

Asked in:

• Dujmović and Wood, On Linear Layouts of Graphs (DMTCS 2004, Section 2).
• Eppstein, Three-Colorable Circle Graphs and Three-Page Book Embeddings (2014).
• Bachmann, 3-coloring Circle Graphs in Theory and Practice, Chapter 6 (master’s thesis, 2022).
• Bachmann, Rutter, and Stumpf, On 3-Coloring Circle Graphs (JGAA 2024, conclusion).
• E S, Ganian, Lokshtanov, and Surianarayanan, A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs (SOSA 2026).

Comments:

• Let N:=|E(G)|=|V(X(G,≺))|. A deterministic N^{O(log N)}-time algorithm decides 3-colorability and constructs a coloring; this is a quasi-polynomial, not polynomial, algorithm.
• For a fixed spine order, assigning stacks is exactly coloring the associated circle graph.
• Two colors are polynomial-time decidable.
• For every fixed number of colors at least 4, the problem is NP-complete.
• A 2023 reexamination identified gaps in earlier claimed solutions and restored the three-color case to open status.

CHROMATIC NUMBER OF QUEUE GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine the maximum chromatic number of q-queue graphs as a function of q.

Discussed in:

• Dujmović and Wood, On Linear Layouts of Graphs (2004, Section 5, Open Problem 3).
• Balko and Poljak, On Off-Diagonal Ordered Ramsey Numbers of Nested Matchings (Discrete Mathematics 2023, Problem 5 and Corollary 8).

Comments:

• Every q-queue graph is 4q-colorable, while for every q≥3 there is a q-queue graph with chromatic number at least 2q+2.
• Every 1-queue graph is 3-colorable, and this is tight.
• For q=2, the maximum lies between 5 and 8; it is open whether every 2-queue graph is 5-colorable.

CHROMATIC NUMBER OF STACK GRAPHSESTIMATED DIFFICULTY: MEDIUM

Problem. Determine the maximum chromatic number of s-stack graphs as a function of s.

Asked in:

• Dujmović and Wood, On Linear Layouts of Graphs (2004, Section 5, Open Problem 2).

Comments:

• For every s, the maximum belongs to {2s, 2s+1, 2s+2}; the complete graph K_2s gives the lower bound 2s.
• The maximum is 3 for s=1 and 4 for s=2.