Pith. sign in

REVIEW 52 references

Weighted book thickness can require more pages than classical book thickness, already for a 10-vertex planar graph and for a 2-tree.

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

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

Weighted book thickness can require strictly more pages than classical book thickness, already for a 10-vertex planar graph and for a 2-tree, but equals the 2-page value for all pathwidth-2 graphs.

T0 review reviewed 2026-07-31 challenge →

load-bearing objection Solid new parameter with clean separations and a linear-time pathwidth-2 algorithm; the 2-tree claim needs a quick cardinality check on the SAT encoding but the rest holds up.

arxiv 2607.24375 v1 pith:5FATG7WK submitted 2026-07-27 cs.CG cs.DM

Weighted Book Thickness

Henry F\"orster , Michael Hoffmann , Stephen Kobourov , Maria Eleni Pavlidi , Alexandra Weinberger , Johannes Zink This is my paper
classification cs.CG cs.DM
keywords book thicknessweighted book thicknesslinear layouts2-treespathwidthouterplanar graphsstack layouts
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

Classical book thickness asks for the fewest pages needed so that edges can be drawn without crossings once vertices sit on a spine. Weighted book thickness instead minimizes the average page number assigned to an edge, treating deeper pages as more expensive. The paper shows that the layouts that achieve the best average need not be the layouts that use the fewest pages: a planar pathwidth-3 graph on ten vertices already forces three pages for the optimum average, and a carefully built 2-tree on ninety-nine vertices does the same. By contrast, every graph of pathwidth at most two admits an optimal weighted embedding on exactly two pages, and that embedding can be built in linear time. Deciding whether the weighted value is at most a given integer remains NP-complete even for planar triangulations.

Core claim

There exist graphs whose weighted book thickness is strictly smaller than their weighted book thickness restricted to bt(G) pages. Concretely, a planar pathwidth-3 graph G on ten vertices satisfies wbt(G)=wbt3(G)=22/19 < wbt2(G)=23/19, and a 2-tree on ninety-nine vertices satisfies wbt3(G)=220/195 < wbt2(G)=221/195; every pathwidth-2 graph, however, satisfies wbt=wbt2 and an optimal two-page embedding is computable in linear time.

What carries the argument

The weighted book thickness wbt(G) is the minimum, over all book embeddings, of the average page index of an edge; the restricted quantity wbt_k(G) forces the embedding to use at most k pages. Separation is proved by exhibiting concrete spine orders and page assignments together with exhaustive outerplanarity and SAT arguments that rule out better averages on fewer pages.

Load-bearing premise

The computer-checked claims for nine-vertex planar graphs and the ninety-nine-vertex 2-tree rest on the correctness of a custom SAT encoding of outerplanarity and page-assignment constraints.

What would settle it

Exhibit either a two-page book embedding of the ten-vertex planar graph whose total page-sum is at most 22, or a two-page embedding of the ninety-nine-vertex 2-tree whose total page-sum is at most 220; either finding would collapse the claimed separations.

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

If this is right

  • For pathwidth-2 graphs the cheapest average is always attained already on two pages and can be computed in linear time.
  • Planar graphs on at most nine vertices never need extra pages for the weighted optimum.
  • Even 2-trees can force an extra page when the objective switches from maximum to average page number.
  • Deciding whether weighted book thickness is at most a given integer is NP-complete for planar triangulations.

Where Pith is reading between the lines

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

  • The same average-versus-maximum gap may appear for other linear layout parameters such as queue number or deque number once analogous weighted variants are defined.
  • If the page-cost function grows faster than linear, the gap between the unrestricted weighted optimum and the optimum restricted to bt(G) pages is likely to widen.
  • The linear-time pathwidth-2 algorithm suggests that other bounded-pathwidth classes may still admit efficient weighted optima even when classical thickness is hard.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Circularity Check

0 steps flagged

No circularity: weighted book thickness is a fresh definition; separations and algorithms are proved from outerplanarity minors, Whitney uniqueness, path/treewidth structure, and explicit SAT encodings of those constraints.

full rationale

The paper defines wbt and wbt_k from scratch (Section 2) as min average page index over book embeddings, then derives bounds and separations by standard combinatorial arguments: outerplanarity forbidden subdivisions (Theorem 1 / Chartrand–Harary), Whitney uniqueness of 3-connected planar embeddings, known pathwidth characterizations (Barát et al.), and explicit counting of edges forced off Page 1 via K_{2,3}/K_{2,4} subdivisions (Lemmas 9–10). The computer-aided parts (Theorems 6–7) encode precisely those derived missing-edge constraints into an external SAT framework (Bekos–Kaufmann–Zielke variables σ, ϕ, χ) and report UNSAT; the encodings are not fitted to a target ratio, nor do they redefine wbt in terms of itself. NP-completeness is a direct reduction from planar Hamiltonicity. Pathwidth-2 optimality (Theorem 13) constructs a maximum outerplanar subgraph by a linear-time marking procedure and exhibits a separating subhamiltonian cycle. No step equates a claimed prediction to a fitted input or to a self-citation uniqueness theorem. The skeptic’s cardinality remark on Lemma 10 is a possible correctness gap, not a circular reduction. Score 0 is therefore appropriate.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 2 invented entities

Load-bearing background is standard structural graph theory (outerplanarity, book embeddings, pathwidth characterizations, Hamiltonicity NP-completeness on triangulations). No numeric free parameters. The only paper-specific inventions are the weighted parameter itself and the sunflower gadget used in the 2-tree separation.

axioms (5)
  • standard math A graph is outerplanar iff it contains no subdivision of K2,3 or K4 (Chartrand–Harary).
    Invoked repeatedly to force edges off Page 1 (Theorem 1; Lemmas 9–10; Claims 15–16).
  • standard math 3-connected planar graphs have a unique embedding up to reflection (Whitney).
    Used in Theorem 5 to argue every 2-page embedding respects the unique plane embedding of the 10-vertex graph.
  • standard math Biconnected pathwidth-2 graphs consist of two paths P,Q joined by noncrossing chords and length-2 paths (Barát–Hajnal–Lin–Yang).
    Structural starting point of the linear-time algorithm in Theorem 13 / Claim 14.
  • standard math Hamiltonicity of planar triangulations is NP-complete (Wigderson).
    Source problem for the NP-completeness reduction in Theorem 4.
  • domain assumption A graph admits a 2-page book embedding iff it is subhamiltonian.
    Classical fact used throughout to equate 2-page layouts with planar Hamiltonian supergraphs.
invented entities (2)
  • weighted book thickness wbt(G) / wbt_k(G) no independent evidence
    purpose: Average-page-cost analogue of classical book thickness.
    Defined in §2 as min average page index over book embeddings; the whole paper studies this new parameter.
  • sunflower graph S and the 99-vertex 2-tree G built from 12 copies around a triangle no independent evidence
    purpose: Gadget witnessing wbt3 < wbt2 for treewidth 2.
    Constructed in §6; separation relies on exhaustive missing-edge constraints derived from S.

reviewed 2026-07-31 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Weighted Book Thickness." pith.science (2026). https://pith.science/paper/5FATG7WK

@misc{pith2026260724375,
  author       = {Pith},
  title        = {Pith review of: Weighted Book Thickness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5FATG7WK}},
  note         = {Machine review of arXiv:2607.24375}
}
Share X Bluesky LinkedIn Reddit HN
abstract

We introduce and study the weighted book thickness of graphs. A $k$-page book embedding of a graph $G=(V,E)$ is defined by a spanning cycle $C$ for $V$ (which does not need to be part of $G$) and a partition $E=\bigcup_{i=1}^{k}E_i$ such that $E\cap C\subseteq E_1$ and each graph $G_i=(V,E_i\cup C)$, for $1 \le i \le k$, is outerplane with outer cycle $C$. If $e\in E_i$, we say that $e$ appears on Page $i$. The classical book thickness of a graph $G$ is the minimum $k$ such that there exists a $k$-page book embedding of $G$, that is, the minimum (over all book embeddings of $G$) achievable maximum page an edge appears on. In contrast, the weighted book thickness is the minimum achievable average page an edge appears on. The embeddings that realize weighted book thickness can differ from those that realize (classical) book thickness. We show that, although every planar graph on at most nine vertices admits a 2-page book embedding realizing its weighted book thickness, already for ten vertices, there is a planar graph for which every realization of its weighted book thickness needs more pages than its book thickness. We prove that there even exists a 2-tree whose weighted book thickness cannot be realized on two pages. On the positive side, we show that for every graph of pathwidth at most two, the weighted book thickness can always be realized by a 2-page book embedding and such an embedding can be found in linear time. Moreover, we prove that it is NP-complete to decide if the weighted book thickness is at most $k$, for some given integer $k$.

discussion (0)

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

Reference graph

Works this paper leans on

52 extracted references · 29 canonical work pages

  1. [1]

    J. F. Balow. Cost optimization of pipe sewerage systems. Proceedings of the Institution of Civil Engineers , 53(1):57--64, 06 1972. https://doi.org/10.1680/iicep.1972.5576 doi:10.1680/iicep.1972.5576

    arXiv 1972

  2. [2]

    On the structure of graphs with path-width at most two

    J \' a nos Bar \' a t, P \' e ter Hajnal, Yixun Lin, and Aifeng Yang. On the structure of graphs with path-width at most two. Studia Scientiarum Mathematicarum Hungarica , 49(2):211--222, 2012. https://doi.org/10.1556/sscmath.49.2012.2.1200 doi:10.1556/sscmath.49.2012.2.1200

    work page doi:10.1556/sscmath.49.2012.2.1200 2012

  3. [3]

    Crossing reduction in circular layouts

    Michael Baur and Ulrik Brandes. Crossing reduction in circular layouts. In Juraj Hromkovic, Manfred Nagl, and Bernhard Westfechtel, editors, Proc. 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004) , volume 3353 of Lecture Notes in Computer Science , pages 332--343. Springer, 2004. https://doi.org/10.1007/978-3-540-30559...

    work page doi:10.1007/978-3-540-30559-0 2004

  4. [4]

    Bekos, Stefan Felsner, Philipp Kindermann, Stephen G

    Michael A. Bekos, Stefan Felsner, Philipp Kindermann, Stephen G. Kobourov, Jan Kratochv \' l, and Ignaz Rutter. The rique-number of graphs. In Patrizio Angelini and Reinhard von Hanxleden, editors, Proc. 30th International Symposium on Graph Drawing and Network Visualization (GD 2022) , Lecture Notes in Computer Science, pages 371--386. Springer, 2022. ht...

    doi:10.1007/978-3-031-22203-0 2022

  5. [5]

    Bekos, Mirco Haug, Michael Kaufmann, and Julia M \" a nnecke

    Michael A. Bekos, Mirco Haug, Michael Kaufmann, and Julia M \" a nnecke. An online framework to interact and efficiently compute linear layouts of graphs. CoRR , abs/2003.09642, 2020. https://arxiv.org/abs/2003.09642 arXiv:2003.09642

    Pith/arXiv arXiv 2003

  6. [6]

    Bekos, Michael Kaufmann, Fabian Klute, Sergey Pupyrev, Chrysanthi N

    Michael A. Bekos, Michael Kaufmann, Fabian Klute, Sergey Pupyrev, Chrysanthi N. Raftopoulou, and Torsten Ueckerdt. Four pages are indeed necessary for planar graphs. J. Comput. Geom. , 11(1):332--353, 2020. https://doi.org/10.20382/JOCG.V11I1A12 doi:10.20382/JOCG.V11I1A12

    work page doi:10.20382/jocg.v11i1a12 2020

  7. [7]

    Bekos, Michael Kaufmann, Maria Eleni Pavlidi, and Xenia Rieger

    Michael A. Bekos, Michael Kaufmann, Maria Eleni Pavlidi, and Xenia Rieger. On the deque and rique numbers of complete and complete bipartite graphs. In Denis Pankratov, editor, Proc. 35th Canadian Conference on Computational Geometry (CCCG 2023) , pages 89--95, 2023. URL: https://wadscccg2023.encs.concordia.ca/assets/pdf/CCCG_2023_proc.pdf

    2023

  8. [8]

    Bekos, Michael Kaufmann, and Christian Zielke

    Michael A. Bekos, Michael Kaufmann, and Christian Zielke. The book embedding problem from a SAT -solving perspective. In Emilio Di Giacomo and Anna Lubiw, editors, Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015) , volume 9411 of LNCS , pages 125--138. Springer, 2015. https://doi.org/10.1007/978-3-319-27261-0 \_11 do...

    work page doi:10.1007/978-3-319-27261-0 2015

  9. [9]

    Frank Bernhart and Paul C. Kainen. The book thickness of a graph. Journal of Combinatorial Theory, Series B , 27(3):320--331, 1979. https://doi.org/10.1016/0095-8956(79)90021-2 doi:10.1016/0095-8956(79)90021-2

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

  10. [10]

    T\' o th, and Manuel Wettstein

    Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. T\' o th, and Manuel Wettstein. Arc diagrams, flip distances, and H amiltonian triangulations. In Proc. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) , volume 30 of Leibniz Internat. Proc. Informatics (LIPIcs) , pages 197--210. Schloss Dagstuhl--Leibniz-Zentr...

    work page doi:10.4230/lipics.stacs.2015.197 2015

  11. [11]

    T\' o th, and Manuel Wettstein

    Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. T\' o th, and Manuel Wettstein. Arc diagrams, flip distances, and H amiltonian triangulations. Comput. Geom. , 68:206--225, 2018. https://doi.org/10.1016/j.comgeo.2017.06.001 doi:10.1016/j.comgeo.2017.06.001

    work page doi:10.1016/j.comgeo.2017.06.001 2018

  12. [12]

    Planar permutation graphs

    Gary Chartrand and Frank Harary. Planar permutation graphs. Annales de l' Institut Henri Poincar \'e - Probabilit \'e s et Statistiques , 3:433--438, 1967. URL: https://eudml.org/doc/76875

    1967

  13. [13]

    Fan R. K. Chung, Frank Thomson Leighton, and Arnold L. Rosenberg. Embedding graphs in books: A layout problem with applications to VLSI design. SIAM Journal on Algebraic and Discrete Methods , 8(1):33--58, 1987. https://doi.org/10.1137/0608002 doi:10.1137/0608002

    work page doi:10.1137/0608002 1987

  14. [14]

    Linear layouts of graphs with priority queues

    Emilio Di Giacomo , Walter Didimo, Henry F \" o rster, Torsten Ueckerdt, and Johannes Zink. Linear layouts of graphs with priority queues. In Pat Morin and Eunjin Oh, editors, Proc. 19th International Symposium on Algorithms and Data Structures (WADS 2025) , LIPIcs, pages 29:1--29:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2025. https://d...

    work page doi:10.4230/lipics.wads.2025.29 2025

  15. [15]

    Emilio Di Giacomo , Walter Didimo, Giuseppe Liotta, and Stephen K. Wismath. Curve-constrained drawings of planar graphs. Comput. Geom. , 30(1):1--23, 2005. https://doi.org/10.1016/J.COMGEO.2004.04.002 doi:10.1016/J.COMGEO.2004.04.002

    work page doi:10.1016/j.comgeo.2004.04.002 2005

  16. [16]

    Emilio Di Giacomo , Walter Didimo, Giuseppe Liotta, and Stephen K. Wismath. Book embeddability of series-parallel digraphs. Algorithmica , 45(4):531--547, 2006. https://doi.org/10.1007/S00453-005-1185-7 doi:10.1007/S00453-005-1185-7

    work page doi:10.1007/s00453-005-1185-7 2006

  17. [17]

    Dillencourt, David Eppstein, and Daniel S

    Michael B. Dillencourt, David Eppstein, and Daniel S. Hirschberg. Geometric thickness of complete graphs. In Sue Whitesides, editor, Proc. 6th International Symposium on Graph Drawing (GD 1998) , volume 1547 of Lecture Notes in Computer Science , pages 101--110. Springer, 1998. https://doi.org/10.1007/3-540-37623-2\_8 doi:10.1007/3-540-37623-2\_8

    work page doi:10.1007/3-540-37623-2 1998

  18. [18]

    Dillencourt, David Eppstein, and Daniel S

    Michael B. Dillencourt, David Eppstein, and Daniel S. Hirschberg. Geometric thickness of complete graphs. In Graph Algorithms And Applications 2 , pages 39--51. World Scientific, 2004. https://doi.org/10.1142/9789812794741_0004 doi:10.1142/9789812794741_0004

    work page doi:10.1142/9789812794741_0004 2004

  19. [19]

    Vida Dujmovic and David R. Wood. Graph treewidth and geometric thickness parameters. In Patrick Healy and Nikola S. Nikolov, editors, Proc. 13th International Symposium on Graph Drawing (GD 2005) , volume 3843 of Lecture Notes in Computer Science , pages 129--140. Springer, 2005. https://doi.org/10.1007/11618058\_13 doi:10.1007/11618058\_13

    work page doi:10.1007/11618058 2005

  20. [20]

    Vida Dujmovi \' c and David R. Wood. Graph treewidth and geometric thickness parameters. Disc. & Comp. Geom. , 37(4):641--670, 2007. https://doi.org/10.1007/s00454-007-1318-7 doi:10.1007/s00454-007-1318-7

    work page doi:10.1007/s00454-007-1318-7 2007

  21. [21]

    Christian A. Duncan. On graph thickness, geometric thickness, and separator theorems. Comput. Geom. , 44(2):95--99, 2011. https://doi.org/10.1016/J.COMGEO.2010.09.005 doi:10.1016/J.COMGEO.2010.09.005

    work page doi:10.1016/j.comgeo.2010.09.005 2011

  22. [22]

    To connect or not to connect? M odelling the optimal degree of centralisation for wastewater infrastructures

    Sven Eggimann, Bernhard Truffer, and Max Maurer. To connect or not to connect? M odelling the optimal degree of centralisation for wastewater infrastructures. Water Research , 84:218--231, 2015. https://doi.org/10.1016/j.watres.2015.07.004 doi:10.1016/j.watres.2015.07.004

    work page doi:10.1016/j.watres.2015.07.004 2015

  23. [23]

    Separating geometric thickness from book thickness

    David Eppstein. Separating geometric thickness from book thickness. arXiv preprint , 2001. https://arxiv.org/abs/math/0109195 arXiv:math/0109195

    Pith/arXiv arXiv 2001

  24. [24]

    Separating thickness from geometric thickness

    David Eppstein. Separating thickness from geometric thickness. In Proc. 10th International Symposium on Graph Drawing (GD 2002) , pages 150--162. Springer, 2002. https://doi.org/10.1007/3-540-36151-0_15 doi:10.1007/3-540-36151-0_15

    work page doi:10.1007/3-540-36151-0_15 2002

  25. [25]

    Graphs that require many colors to achieve their chromatic sum

    Paul Erd o s, Ewa Kubicka, and Allen Schwenk. Graphs that require many colors to achieve their chromatic sum. Congr. Numer. , 71, 1990

    1990

  26. [26]

    orster. Graph Drawing Beyond the Beaten Tracks . PhD thesis, Universit\

    Henry F\"orster. Graph Drawing Beyond the Beaten Tracks . PhD thesis, Universit\"at T\"ubingen, 2020. URL: http://hdl.handle.net/10900/108847

    2020

  27. [27]

    Ganley and Lenwood Heath

    Joseph L. Ganley and Lenwood Heath. The pagenumber of k -trees is O(k) . Disc. App. Math. , 109(3):215--221, 2001. https://doi.org/10.1016/S0166-218X(00)00178-5 doi:10.1016/S0166-218X(00)00178-5

    work page doi:10.1016/s0166-218x(00)00178-5 2001

  28. [28]

    A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs

    Krzysztof Giaro, Robert Janczewski, Marek Kubale, and Michal Malafiejski. A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs. In Klaus Jansen, Stefano Leonardi, and Vijay V. Vazirani, editors, Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002) , volume 2462 of Lecture N...

    work page doi:10.1007/3-540-45753-4 2002

  29. [29]

    Goldner and F

    A. Goldner and F. Harary. Note on a smallest nonhamiltonian maximal planar graph. Bulletin of the Malaysian Math. Sci. Soc. , 1(6):41--42, 1975

    1975

  30. [30]

    Algorithms for Incremental Planar Graph Drawing and Two-page Book Embeddings

    Martin Gronemann. Algorithms for Incremental Planar Graph Drawing and Two-page Book Embeddings . PhD thesis, University of Cologne, 2015. URL: http://kups.ub.uni-koeln.de/id/eprint/6329

    2015

  31. [31]

    Halld \' o rsson, Guy Kortsarz, and Hadas Shachnai

    Magn \' u s M. Halld \' o rsson, Guy Kortsarz, and Hadas Shachnai. Minimizing average completion of dedicated tasks and interval graphs. In Michel X. Goemans, Klaus Jansen, Jos \' e D. P. Rolim, and Luca Trevisan, editors, Proc. 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2001) , volume 2129 of Le...

    work page doi:10.1007/3-540-44666-4 2001

  32. [32]

    Embedding planar graphs in seven pages

    Lenwood Heath. Embedding planar graphs in seven pages. In Proc. 25th Annual Symposium on Foundations of Computer Science (FOCS 1984) , pages 74--83. IEEE Comp. Soc., 1984. https://doi.org/10.1109/SFCS.1984.715903 doi:10.1109/SFCS.1984.715903

    arXiv 1984

  33. [33]

    Heath and Arnold L

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

    work page doi:10.1137/0221055 1992

  34. [34]

    Hopcroft and Robert Endre Tarjan

    John E. Hopcroft and Robert Endre Tarjan. Efficient algorithms for graph manipulation [H] (algorithm 447). Commun. ACM , 16(6):372--378, 1973. https://doi.org/10.1145/362248.362272 doi:10.1145/362248.362272

    arXiv 1973

  35. [35]

    Paul C. Kainen. Thickness and coarseness of graphs. In Abhandlungen aus dem Mathematischen Seminar der Universit \"a t Hamburg , volume 39, pages 88--95. Springer, 1973. https://doi.org/10.1007/bf02992822 doi:10.1007/bf02992822

    work page doi:10.1007/bf02992822 1973

  36. [36]

    Ewa M. Kubicka. Polynomial algorithm for finding chromatic sum for unicyclic and outerplanar graphs. Ars Comb. , 76, 2005

    2005

  37. [37]

    Kubicka and Allen J

    Ewa M. Kubicka and Allen J. Schwenk. An introduction to chromatic sums. In Arthur M. Riehl, editor, Proc. 1989 ACM 17th Annual Computer Science Conference (CSC 1989) , pages 39--45. ACM , 1989. https://doi.org/10.1145/75427.75430 doi:10.1145/75427.75430

    arXiv 1989

  38. [38]

    An annotated bibliography on the thickness, outerthickness, and arboricity of a graph

    Erkki M \"a kinen and Timo Poranen. An annotated bibliography on the thickness, outerthickness, and arboricity of a graph. Missouri Journal of Mathematical Sciences , 24(1), 2012. https://doi.org/10.35834/mjms/1337950501 doi:10.35834/mjms/1337950501

    arXiv 2012

  39. [39]

    A short proof of the NP -completeness of minimum sum interval coloring

    D \' a niel Marx. A short proof of the NP -completeness of minimum sum interval coloring. Oper. Res. Lett. , 33(4):382--384, 2005. https://doi.org/10.1016/J.ORL.2004.07.006 doi:10.1016/J.ORL.2004.07.006

    work page doi:10.1016/j.orl.2004.07.006 2005

  40. [40]

    The thickness of graphs: A survey

    Petra Mutzel, Thomas Odenthal, and Mark Scharbrodt. The thickness of graphs: A survey. Graphs Comb. , 14(1):59--73, 1998. https://doi.org/10.1007/PL00007219 doi:10.1007/PL00007219

    work page doi:10.1007/pl00007219 1998

  41. [41]

    T. Ollmann. On the book thicknesses of various graphs. In F. Hoffman, R.B. Levow, and R.S.D. Thomas, editors, Southeastern Conference on Combinatorics, Graph Theory and Computing , volume VIII of Cong. Num. , page 459, 1973

    1973

  42. [42]

    Mixed linear layouts of planar graphs

    Sergey Pupyrev. Mixed linear layouts of planar graphs. In Fabrizio Frati and Kwan - Liu Ma, editors, Proc. 25th International Symposium on Graph Drawing and Network Visualization (GD 2017) , volume 10692 of LNCS , pages 197--209. Springer, 2017. https://doi.org/10.1007/978-3-319-73915-1\_17 doi:10.1007/978-3-319-73915-1\_17

    doi:10.1007/978-3-319-73915-1 2017

  43. [43]

    Rengarajan and C

    S. Rengarajan and C. E. Veni Madhavan. Stack and queue number of 2-trees. In Ding - Zhu Du and Ming Li, editors, Proc. 1st Annual International Conference on Computing and Combinatorics (COCOON 1995) , volume 959 of LNCS , pages 203--212. Springer, 1995. https://doi.org/10.1007/BFb0030834 doi:10.1007/BFb0030834

    work page doi:10.1007/bfb0030834 1995

  44. [44]

    Stow, Yuan Xie, Taniya Siddiqua, and Gabriel H

    Dylan C. Stow, Yuan Xie, Taniya Siddiqua, and Gabriel H. Loh. Cost-effective design of scalable high-performance systems using active and passive interposers. In Sri Parameswaran, editor, Proc. 2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2017) , pages 728--735. IEEE , 2017. https://doi.org/10.1109/ICCAD.2017.8203849 doi:10.1109/...

    arXiv 2017

  45. [45]

    Kenneth J. Supowit. Finding a maximum planar subset of a set of nets in a channel. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. , 6(1):93--94, 1987. https://doi.org/10.1109/TCAD.1987.1270250 doi:10.1109/TCAD.1987.1270250

    arXiv 1987

  46. [46]

    W.T. Tutte. The thickness of a graph. Indagationes Mathematicae (Proceedings) , 66:567--577, 1963. https://doi.org/10.1016/S1385-7258(63)50055-9 doi:10.1016/S1385-7258(63)50055-9

    work page doi:10.1016/s1385-7258(63)50055-9 1963

  47. [47]

    Arc diagrams: Visualizing structure in strings

    Martin Wattenberg. Arc diagrams: Visualizing structure in strings. In Pak Chung Wong and Keith Andrews, editors, 2002 IEEE Symposium on Information Visualization (InfoVis 2002) , pages 110--116. IEEE Computer Society, 2002. https://doi.org/10.1109/INFVIS.2002.1173155 doi:10.1109/INFVIS.2002.1173155

    Pith/arXiv arXiv 2002

  48. [48]

    Congruent graphs and the connectivity of graphs

    Hassler Whitney. Congruent graphs and the connectivity of graphs. American Journal of Mathematics , 54(1):150--168, 1932. https://doi.org/10.2307/2371086 doi:10.2307/2371086

    doi:10.2307/2371086 1932

  49. [49]

    The complexity of the H amiltonian circuit problem for maximal planar graphs

    Avi Wigderson. The complexity of the H amiltonian circuit problem for maximal planar graphs. Technical Report 298, Dep. of Electrical Eng. and Comp. Science, Princeton University, 1982

    1982

  50. [50]

    Four pages are necessary and sufficient for planar graphs (extended abstract)

    Mihalis Yannakakis. Four pages are necessary and sufficient for planar graphs (extended abstract). In Juris Hartmanis, editor, Proc. 18th Annual ACM Symposium on Theory of Computing (STOC 1986) , pages 104--108. ACM , 1986. https://doi.org/10.1145/12130.12141 doi:10.1145/12130.12141

    arXiv 1986

  51. [51]

    Embedding planar graphs in four pages

    Mihalis Yannakakis. 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 doi:10.1016/0022-0000(89)90032-9

    work page doi:10.1016/0022-0000(89)90032-9 1989

  52. [52]

    Planar graphs that need four pages

    Mihalis Yannakakis. Planar graphs that need four pages. J. Comb. Theory, Ser. B , 145:241--263, 2020. https://doi.org/10.1016/j.jctb.2020.05.008 doi:10.1016/j.jctb.2020.05.008

    work page doi:10.1016/j.jctb.2020.05.008 2020

This paper was first reviewed by grok-4.5 on July 31, 2026.