Embedding planar graphs in four pages
From MaRDI portal
Publication:1120582
DOI10.1016/0022-0000(89)90032-9zbMath0673.05022DBLPjournals/jcss/Yannakakis89OpenAlexW2119115989WikidataQ56689179 ScholiaQ56689179MaRDI QIDQ1120582
Publication date: 1989
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(89)90032-9
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory to circuits and networks (94C15)
Related Items (94)
The longest common subsequence problem for sequences with nested arc annotations. ⋮ On certain Hamiltonian inner triangulations ⋮ Planar drawings with few slopes of Halin graphs and nested pseudotrees ⋮ Embedding generalized Petersen graph in books ⋮ Parameterized Algorithms for Queue Layouts ⋮ Two-page book embeddings of 4-planar graphs ⋮ Book embedding of locally planar graphs on orientable surfaces ⋮ A survey on book-embedding of planar graphs ⋮ Stack-number is not bounded by queue-number ⋮ On the queue number of planar graphs ⋮ Approximation of the Quadratic Knapsack Problem ⋮ On simultaneous planar graph embeddings ⋮ The mixed page number of graphs ⋮ Embedding de Bruijn, Kautz and shuffle-exchange networks in books ⋮ The pagenumber of toroidal graphs is at most seven ⋮ Parameterized analysis and crossing minimization problems ⋮ Fan-crossing free graphs and their relationship to other beyond-planar graphs ⋮ An annotated bibliography on 1-planarity ⋮ Layered separators in minor-closed graph classes with applications ⋮ The book thickness of 1-planar graphs is constant ⋮ 1-page and 2-page drawings with bounded number of crossings per edge ⋮ RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties ⋮ Embedding planar 5-graphs in three pages ⋮ Small Point Sets for Simply-Nested Planar Graphs ⋮ On the Page Number of Upward Planar Directed Acyclic Graphs ⋮ Straight-line drawings of 1-planar graphs ⋮ A Sublinear Bound on the Page Number of Upward Planar Graphs ⋮ Upward book embeddability of \(st\)-graphs: complexity and algorithms ⋮ Book embeddings of \(k\)-framed graphs and \(k\)-map graphs ⋮ A metric for rooted trees with unlabeled vertices based on nested parentheses ⋮ Graphs of linear growth have bounded treewidth ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ The Rique-number of graphs ⋮ An improved upper bound on the queue number of planar graphs ⋮ Stack and Queue Layouts via Layered Separators ⋮ Succinct representation of labeled graphs ⋮ Linear layouts of bipartite planar graphs ⋮ Efficient deterministic algorithms for embedding graphs on books ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Planar graphs that need four pages ⋮ Bijections for Baxter families and related objects ⋮ Parameterized algorithms for book embedding problems ⋮ Local and union page numbers ⋮ Mixed linear layouts: complexity, heuristics, and experiments ⋮ Book drawings of complete bipartite graphs ⋮ Finding Hamiltonian cycles in certain planar graphs ⋮ Orthogonal drawings of graphs for the automation of VLSI circuit design ⋮ Mixed Linear Layouts of Planar Graphs ⋮ Upward Partitioned Book Embeddings ⋮ Experimental Evaluation of Book Drawing Algorithms ⋮ Beyond Outerplanarity ⋮ Graph layouts via layered separators ⋮ Computing Upward Topological Book Embeddings of Upward Planar Digraphs ⋮ Parameterized Algorithms for Book Embedding Problems ⋮ Characterisations and examples of graph classes with bounded expansion ⋮ Equipartitions of graphs ⋮ Data Structures and their Planar Graph Layouts ⋮ The pagenumber of the class of bandwidth-k graphs is \(k-1\) ⋮ Simpler algorithms for testing two-page book embedding of partitioned graphs ⋮ Deciding whether graph \(G\) has page number one is in NC ⋮ Small universal point sets for \(k\)-outerplanar graphs ⋮ On the queue-number of graphs with bounded tree-width ⋮ Computing upward topological book embeddings of upward planar digraphs ⋮ The pagenumber of \(k\)-trees is \(O(k)\) ⋮ Unnamed Item ⋮ Curve-constrained drawings of planar graphs ⋮ Structural properties of subdivided-line graphs ⋮ Planar graphs, via well-orderly maps and trees ⋮ On dispersable book embeddings ⋮ Queue layouts of planar 3-trees ⋮ Book embedding of complex network with community structure ⋮ Crossing-Optimal Acyclic Hamiltonian Path Completion and Its Application to Upward Topological Book Embeddings ⋮ Queue layouts of planar 3-trees ⋮ Recognizing DAGs with page-number 2 is NP-complete ⋮ Planar and grid graph reachability problems ⋮ Unnamed Item ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Fast and compact planar embeddings ⋮ On exteriority notions in book embeddings and treewidth ⋮ On the upward book thickness problem: combinatorial and complexity results ⋮ Upward Book Embeddings of st-Graphs ⋮ The Same Upper Bound for Both: The 2-page and the Rectilinear Crossing Numbers of then-Cube ⋮ Improved book-embeddings of incomplete hypercubes ⋮ Planar Graphs of Bounded Degree Have Bounded Queue Number ⋮ Characterizations of Deque and Queue Graphs ⋮ Book Embedding of Graphs on the Projective Plane ⋮ Embedding the incomplete hypercube in books ⋮ On mixed linear layouts of series-parallel graphs ⋮ Book Embeddings of Regular Graphs ⋮ Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph ⋮ Parameterized Algorithms for Queue Layouts ⋮ On Mixed Linear Layouts of Series-Parallel Graphs ⋮ On Page Number of N-free Posets ⋮ Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)
Cites Work
This page was built for publication: Embedding planar graphs in four pages
