Embedding planar graphs in four pages
From MaRDI portal
A book embedding of a graph is an embedding of the vertices along the spine of a ``book (i.e., a linear ordering of the vertices) together with an embedding of its edges on the pages so that edges placed in the same page do not intersect. The author proves that any planar graph has a book embedding with at most four pages. The proof is constructive. Moreover, a linear time algorithm is presented for finding such an embedding. In another paper of the author (which is in preparation), examples of planar graphs are constructed which do not admit a book embedding with 3 pages.
Recommendations
Cites work
- Efficient Planarity Testing
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 4128415 (Why is no real title available?)
- scientific article; zbMATH DE number 3420624 (Why is no real title available?)
- Sorting Using Networks of Queues and Stacks
- The book thickness of a graph
- The Complexity of Coloring Circular Arcs and Chords
Cited in
(only showing first 100 items - show all)- Improved book-embeddings of incomplete hypercubes
- Embedding the incomplete hypercube in books
- A trade-off between page number and page width of book embeddings of graphs
- Equipartitions of graphs
- Deciding whether graph \(G\) has page number one is in NC
- Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
- Embedding de Bruijn, Kautz and shuffle-exchange networks in books
- The pagenumber of toroidal graphs is at most seven
- Optimum embedding of complete graphs in books
- A genetic algorithm for finding the pagenumber of interconnection networks
- 1-page and 2-page drawings with bounded number of crossings per edge
- Simpler algorithms for testing two-page book embedding of partitioned graphs
- The longest common subsequence problem for sequences with nested arc annotations.
- Orthogonal drawings of graphs for the automation of VLSI circuit design
- Small universal point sets for \(k\)-outerplanar graphs
- Structural properties of subdivided-line graphs
- On mixed linear layouts of series-parallel graphs
- Augmenting a tree to a k-arbor-connected graph with pagenumber k
- A survey on book-embedding of planar graphs
- Stack-number is not bounded by queue-number
- On the queue number of planar graphs
- The mixed page number of graphs
- Parameterized analysis and crossing minimization problems
- Embedding planar 5-graphs in three pages
- Planar graphs that need four pages
- Parameterized algorithms for book embedding problems
- Local and union page numbers
- Mixed linear layouts: complexity, heuristics, and experiments
- Computing upward topological book embeddings of upward planar digraphs
- The pagewidth of trivalent planar graphs
- Book embedding of complex network with community structure
- On exteriority notions in book embeddings and treewidth
- On certain Hamiltonian inner triangulations
- An annotated bibliography on 1-planarity
- Layered separators in minor-closed graph classes with applications
- Succinct representation of labeled graphs
- Bijections for Baxter families and related objects
- Book drawings of complete bipartite graphs
- Planar graphs, via well-orderly maps and trees
- Book embedding of locally planar graphs on orientable surfaces
- Fan-crossing free graphs and their relationship to other beyond-planar graphs
- Recognizing DAGs with page-number 2 is NP-complete
- An improved upper bound on the queue number of planar graphs
- The same upper bound for both: the 2-page and the rectilinear crossing numbers of the \(n\)-cube
- Book embedding of toroidal bipartite graphs
- Simpler algorithms for testing two-page book embedding of partitioned graphs
- Embedding graphs in cylinder and torus books
- Embedding generalized Petersen graph in books
- The book embedding problem from a SAT-solving perspective
- Two-page book embeddings of 4-planar graphs
- Oriented book embeddings
- Two-page book embeddings of 4-planar graphs
- Characterizations of deque and queue graphs
- Approximation of the quadratic knapsack problem
- Small point sets for simply-nested planar graphs
- On the page number of upward planar directed acyclic graphs
- On Page Number of N-free Posets
- Embedding the Myceilski of a graph and the amalgamation of two graphs in pages
- On the pagenumber of \(k\)-trees
- Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings
- Embedding quadrangulations on a 2-book
- A metric for rooted trees with unlabeled vertices based on nested parentheses
- scientific article; zbMATH DE number 398966 (Why is no real title available?)
- scientific article; zbMATH DE number 4128415 (Why is no real title available?)
- Embedding de Bruijn and Shuffle-Exchange Graphs in Five Pages
- The pagenumber of genus g graphs is O( g )
- Graphs with E Edges Have Pagenumber O(√E)
- Mixed linear layouts of planar graphs
- Upward partitioned book embeddings
- Experimental evaluation of book drawing algorithms
- Beyond outerplanarity
- Data Structures and their Planar Graph Layouts
- Graph layouts via layered separators
- Implementing a partitioned 2-page book embedding testing algorithm
- Parameterized Algorithms for Queue Layouts
- On Mixed Linear Layouts of Series-Parallel Graphs
- Parameterized algorithms for queue layouts
- Sequentially embeddable graphs
- Triconnected planar graphs of maximum degree five are subhamiltonian
- Upward book embeddings of st-graphs
- An improved fixed-parameter algorithm for one-page crossing minimization
- Four pages are indeed necessary for planar graphs
- A survey on book-embedding of planar graphs
- Parameterized algorithms for book embedding problems
- On the queue-number of graphs with bounded tree-width
- Planar graphs of bounded degree have bounded queue number
- Book embedding of graphs on the projective plane
- Book embeddings of regular graphs
- Computing Upward Topological Book Embeddings of Upward Planar Digraphs
- scientific article; zbMATH DE number 2188384 (Why is no real title available?)
- Queue layouts of planar 3-trees
- On the upward book thickness problem: combinatorial and complexity results
- Queue layouts of planar 3-trees
- On the upward book thickness problem: combinatorial and complexity results
- The pagenumber of k-trees is O(k)
- Straight-line drawings of 1-planar graphs
- A Sublinear Bound on the Page Number of Upward Planar Graphs
- Book embeddings of nonplanar graphs with small faces in few pages
- Upward book embeddability of \(st\)-graphs: complexity and algorithms
- Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
This page was built for publication: Embedding planar graphs in four pages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1120582)
