Genus g Graphs Have Pagenumber O(√g)
From MaRDI portal
Publication:4304062
DOI10.1006/jagm.1994.1028zbMath0810.68103OpenAlexW1980248515WikidataQ56689194 ScholiaQ56689194MaRDI QIDQ4304062
Publication date: 8 September 1994
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1994.1028
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (31)
Book embedding of locally planar graphs on orientable surfaces ⋮ A survey on book-embedding of planar graphs ⋮ Unnamed Item ⋮ Embedding de Bruijn, Kautz and shuffle-exchange networks in books ⋮ The pagenumber of toroidal graphs is at most seven ⋮ Layered separators in minor-closed graph classes with applications ⋮ The book thickness of 1-planar graphs is constant ⋮ RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties ⋮ 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 ⋮ Stack and Queue Layouts via Layered Separators ⋮ Minimize the maximum duty in multi-interface networks ⋮ Efficient deterministic algorithms for embedding graphs on books ⋮ Planar graphs that need four pages ⋮ Unnamed Item ⋮ Geometric thickness in a grid ⋮ Graph layouts via layered separators ⋮ Structural properties of subdivided-line graphs ⋮ On dispersable book embeddings ⋮ Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method ⋮ Min-Max Coverage in Multi-interface Networks ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Unnamed Item ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Upward Book Embeddings of st-Graphs ⋮ Improved book-embeddings of incomplete hypercubes ⋮ Book Embedding of Graphs on the Projective Plane ⋮ Revising Johnson's table for the 21st century ⋮ Book Embeddings of Regular Graphs ⋮ Geometric Thickness in a Grid of Linear Area
This page was built for publication: Genus g Graphs Have Pagenumber O(√g)
