Genus g Graphs Have Pagenumber O(√g)
From MaRDI portal
Publication:4304062
DOI10.1006/jagm.1994.1028zbMath0810.68103WikidataQ56689194 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
Book Embeddings of Regular Graphs, Graph layouts via layered separators, RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties, Improved book-embeddings of incomplete hypercubes, Embedding de Bruijn, Kautz and shuffle-exchange networks in books, The pagenumber of toroidal graphs is at most seven, Geometric thickness in a grid, Structural properties of subdivided-line graphs, Layered separators in minor-closed graph classes with applications, The book thickness of 1-planar graphs is constant, Minimize the maximum duty in multi-interface networks, Book embedding of locally planar graphs on orientable surfaces, Stack and Queue Layouts via Layered Separators, Min-Max Coverage in Multi-interface Networks, On the Page Number of Upward Planar Directed Acyclic Graphs, Geometric Thickness in a Grid of Linear Area, Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method