Pith. sign in

REVIEW 52 references

Weighted Book Thickness

T0 review · reviewed 2026-07-31 · grok-4.5

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

Pith's one-line read Weighted book thickness can require more pages than classical book thickness, already for a 10-vertex planar graph and for a 2-tree.

desk verdict 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. read the letter →

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

Henry Förster , Michael Hoffmann , Stephen Kobourov , Maria Eleni Pavlidi , Alexandra Weinberger , Johannes Zink This is my paper
classification cs.CGcs.DM
keywords bookthicknessweightedlinearlayouts2-treespathwidthouterplanargraphsstack
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

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.

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.

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

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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, and a circularity audit.

Circularity Check

0 steps flagged · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 5 assumptions · 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.

assumptions (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)
    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
    purpose: Gadget witnessing wbt3 < wbt2 for treewidth 2.
    Constructed in §6; separation relies on exhaustive missing-edge constraints derived from S.

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}
}
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 to comment.

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

    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

Show all 52 references
  1. [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

    1979 doi

  2. [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 Intern...

    2015 doi

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

    2018 doi

  4. [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

  5. [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

    1987 doi

  6. [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...

    2025 doi

  7. [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

    2005 doi

  8. [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

    2006 doi

  9. [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...

    1998 doi

  10. [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

    2004 doi

  11. [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, 20...

    2005 doi

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

    2007 doi

  13. [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

    2011 doi

  14. [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

    2015 doi

  15. [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

    2001 arXiv

  16. [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

    2002 doi

  17. [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

  18. [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

  19. [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

    2001 doi

  20. [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 Al...

    2002 doi

  21. [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

  22. [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

  23. [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 Algo...

    2001 doi

  24. [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

    1984

  25. [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

    1992 doi

  26. [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

    1973

  27. [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

    1973 doi

  28. [36]

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

    2005

  29. [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

    1989

  30. [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

    2012

  31. [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

    2005 doi

  32. [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

    1998 doi

  33. [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

  34. [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-3...

    2017 doi

  35. [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.100...

    1995 doi

  36. [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) , page...

    2017

  37. [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

    1987

  38. [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

    1963 doi

  39. [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.11...

    2002 arXiv

  40. [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

    1932 doi

  41. [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

  42. [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

    1986

  43. [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

    1989 doi

  44. [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

    2020 doi

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.