Book embedding of graphs on the projective plane

DOI10.1137/16M1076174MaRDI QIDQ5237910zbMATH OpenOpenAlexWikidataFDO

Authors Kenta Ozeki, Atsuhiro Nakamoto, Takayuki Nozawa

Publication date 25 October 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/16m1076174

zbMATH Keywords

book embeddinggraphs on the projective planeTutte paths

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Embedding planar graphs in four pages
• Embedding planar 5-graphs in three pages
• Book embedding of locally planar graphs on orientable surfaces
• Four pages are indeed necessary for planar graphs

Cites work

• 4-connected projective planar graphs are Hamiltonian
• A theorem on paths in planar graphs
• A Theorem on Planar Graphs
• Book embedding of projective-planar graphs
• Book embeddings of regular graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding planar graphs in four pages
• Genus g Graphs Have Pagenumber O(√g)
• Graph treewidth and geometric thickness parameters
• Graphs with E Edges Have Pagenumber O(√E)
• scientific article; zbMATH DE number 1002024 (Why is no real title available?)
• scientific article; zbMATH DE number 1156578 (Why is no real title available?)
• On Crossing Sets, Disjoint Sets, and Pagenumber
• On Hamilton cycles in certain planar graphs
• On the pagenumber of \(k\)-trees
• On the pagenumber of complete bipartite graphs
• Pagenumber of complete bipartite graphs
• The book thickness of a graph
• The pagenumber of k-trees is O(k)
• The pagenumber of genus g graphs is O( g )
• The pagenumber of toroidal graphs is at most seven

Cited in

(4)

• Book embeddability of series-parallel digraphs
• Book embedding of locally planar graphs on orientable surfaces
• Embedding Outerplanar Graphs in Small Books
• scientific article; zbMATH DE number 6902663 (Why is no real title available?)

This page was built for publication: Book embedding of graphs on the projective plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5237910)