The pagenumber of \(k\)-trees is \(O(k)\)

DOI10.1016/S0166-218X(00)00178-5zbMath0976.68116OpenAlexW2076348790WikidataQ29040940 ScholiaQ29040940MaRDI QIDQ5931789

Joseph L. Ganley, Lenwood S. Heath

Publication date: 25 September 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00178-5

zbMATH Keywords

treewidth\(k\)-treebook embedding

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Book embedding of locally planar graphs on orientable surfaces ⋮ A survey on book-embedding of planar graphs ⋮ The mixed page number of graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ 1-page and 2-page drawings with bounded number of crossings per edge ⋮ On the Page Number of Upward Planar Directed Acyclic Graphs ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ Graphs of linear growth have bounded treewidth ⋮ Planar graphs that need four pages ⋮ Parameterized algorithms for book embedding problems ⋮ Local and union page numbers ⋮ Experimental Evaluation of Book Drawing Algorithms ⋮ Parameterized Algorithms for Book Embedding Problems ⋮ On the queue-number of graphs with bounded tree-width ⋮ Structural properties of subdivided-line graphs ⋮ Upward Book Embeddings of st-Graphs ⋮ Improved book-embeddings of incomplete hypercubes ⋮ Book Embedding of Graphs on the Projective Plane ⋮ Fixed-order book thickness with respect to the vertex-cover number: new observations and further analysis

Cites Work

• Unnamed Item
• Unnamed Item
• The pagenumber of the class of bandwidth-k graphs is \(k-1\)
• Graph minors. III. Planar tree-width
• Embedding planar graphs in four pages
• The book thickness of a graph
• A partial k-arboretum of graphs with bounded treewidth
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Pagenumber of complete bipartite graphs
• Laying Out Graphs Using Queues
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design