Efficient deterministic algorithms for embedding graphs on books

DOI10.1007/3-540-61332-3_149MaRDI QIDQ6184660zbMATH OpenOpenAlexFDO

Authors Farhad Shahrokhi, Weiping Shi

Publication date 29 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61332-3_149

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Degree constrained book embeddings
• Embedding planar graphs in four pages
• Embedding planar 5-graphs in three pages
• Simpler algorithms for testing two-page book embedding of partitioned graphs
• The pagenumber of genus g graphs is O( g )

Cites work

• An inequality for the chromatic number of a graph
• 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)
• Graphs with E Edges Have Pagenumber O(√E)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• Smallest-last ordering and clustering and graph coloring algorithms
• The book thickness of a graph
• The complexity of computing the permanent
• The pagenumber of genus g graphs is O( g )

This page was built for publication: Efficient deterministic algorithms for embedding graphs on books

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