The pagenumber of genus g graphs is O( g )

DOI10.1145/146637.146643zbMath0799.68152OpenAlexW1968377231MaRDI QIDQ4302800

Lenwood S. Heath, Sorin Istrail

Publication date: 13 November 1994

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/146637.146643

zbMATH Keywords

homotopy classessurface embeddingsgraph genusbook embeddingsplanar-nonplanar decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (11)

Book embedding of locally planar graphs on orientable surfaces ⋮ A survey on book-embedding of planar graphs ⋮ A trade-off between page number and page width of book embeddings of graphs ⋮ Embedding de Bruijn, Kautz and shuffle-exchange networks in books ⋮ The pagenumber of toroidal graphs is at most seven ⋮ On the Page Number of Upward Planar Directed Acyclic Graphs ⋮ Efficient deterministic algorithms for embedding graphs on books ⋮ Planar graphs that need four pages ⋮ Local and union page numbers ⋮ Book Embedding of Graphs on the Projective Plane ⋮ Book Embeddings of Regular Graphs

This page was built for publication: The pagenumber of genus g graphs is O( g )