Embedding Planar Graphs In Seven Pages

2005/08/25 by Lenwood S. Heath · 2 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Book embedding #Planar graph #Embedding #Planar straight-line graph #Planar #Outerplanar graph #Polyhedral graph #Conjecture #Computer science #Graph #Combinatorics #Graph embedding #Discrete mathematics #Mathematics #1-planar graph #Pathwidth #Theoretical computer science #Chordal graph #Line graph #Artificial intelligence #Computer graphics (images)

paper · doi:10.1109/sfcs.1984.715903

openalex publication_date 2005/08/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

This paper investigates the problem of embedding planar graphs in books of few pages. An efficient algorithm for embedding a planar graph in a book establishes an upper bound of seven pages for any planar graph. This disproves a conjecture of Bernhart and Kainen that the pagenumber of a planar graph can be arbitrarily large. It is also shown that the stellations of K/sub 3/ have pagenumber three, the best possible.

Cited by

• On 3-pushdown graphs with large separators
• Four pages are necessary and sufficient for planar graphs
• A trade-off between page number and page width of book embeddings of graphs
• 1-Planar Graphs have Constant Book Thickness
• Embedding planar graphs in four pages
• Book embedding [wikipedia]