Embedding planar 5-graphs in three pages

DOI10.1016/J.DAM.2019.11.020MaRDI QIDQ2185736zbMATH OpenOpenAlexWikidataFDO

Authors Xiaxia Guan, Weihua Yang

Publication date 5 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.07097

zbMATH Keywords

book embeddingpagenumberplanar graph

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)

Abstract: A emph{book-embedding} of a graph $G$ is an embedding of vertices of $G$ along the spine of a book, and edges of $G$ on the pages so that no two edges on the same page intersect. the minimum number of pages in which a graph can be embedded is called the emph{page number}. The book-embedding of graphs may be important in several technical applications, e.g., sorting with parallel stacks, fault-tolerant processor arrays design, and layout problems with application to very large scale integration (VLSI). Bernhart and Kainen firstly considered the book-embedding of the planar graph and conjectured that its page number can be made arbitrarily large [JCT, 1979, 320-331]. Heath [FOCS84] found that planar graphs admit a seven-page book embedding. Later, Yannakakis proved that four pages are necessary and sufficient for planar graphs in [STOC86]. Recently, Bekos et al. [STACS14] described an $O(n^2)$ time algorithm of two-page book embedding for 4-planar graphs. In this paper, we embed 5-planar graphs into a book of three pages by an $O(n^2)$ time algorithm.

Recommendations

• Embedding planar graphs in four pages
• Four pages are indeed necessary for planar graphs
• A survey on book-embedding of planar graphs
• A survey on book-embedding of planar graphs

Cites work

• A genetic algorithm for finding the pagenumber of interconnection networks
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding planar graphs in four pages
• Graph theory with applications
• Graph treewidth and geometric thickness parameters
• Hamiltonian circuits in simplicial complexes
• scientific article; zbMATH DE number 4128415 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• On the pagenumber of complete bipartite graphs
• Optimum embedding of complete graphs in books
• Ordered sets, pagenumbers and planarity
• Pagenumber of complete bipartite graphs
• The book embedding problem from a SAT-solving perspective
• The book thickness of a graph
• Triconnected planar graphs of maximum degree five are subhamiltonian
• Two-page book embeddings of 4-planar graphs

Cited in

(22)

• Embedding planar graphs in four pages
• On mixed linear layouts of series-parallel graphs
• A survey on book-embedding of planar graphs
• Recognizing DAGs with page-number 2 is NP-complete
• Two-page book embeddings of 4-planar graphs
• Two-page book embeddings of 4-planar graphs
• Bounding the number of embeddings of 5-connected projective-planar graphs
• scientific article; zbMATH DE number 4128415 (Why is no real title available?)
• Implementing a partitioned 2-page book embedding testing algorithm
• On Mixed Linear Layouts of Series-Parallel Graphs
• Triconnected planar graphs of maximum degree five are subhamiltonian
• Four pages are indeed necessary for planar graphs
• Book embedding of graphs on the projective plane
• Book embeddings of nonplanar graphs with small faces in few pages
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• Recognizing DAGs with page-number 2 is NP-complete
• The Rique-number of graphs
• Efficient deterministic algorithms for embedding graphs on books
• Using Euler’s Formula to Find the Lower Bound of the Page Number
• On the stack layouts of toroidal grids
• Directed acyclic outerplanar graphs have constant stack number
• Queue layouts on folded hypercubes

This page was built for publication: Embedding planar 5-graphs in three pages

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