Upward book embeddability of \(st\)-graphs: complexity and algorithms
From MaRDI portal
Publication:6066758
DOI10.1007/s00453-023-01142-yMaRDI QIDQ6066758
Tamara Mchedlidze, Giordano Da Lozzo, Maurizio Patrignani, Walter Didimo, Carla Binucci, Emilio Di Giacomo
Publication date: 13 December 2023
Published in: Algorithmica (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Two-page book embeddings of 4-planar graphs
- Upward planar drawings on the standing and the rolling cylinders
- Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph
- Strip planarity testing for embedded planar graphs
- Curve-constrained drawings of planar graphs
- Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices
- Ordered sets, pagenumbers and planarity
- Drawing colored graphs on colored points
- Drawing colored graphs with constrained vertex positions and few bends per edge
- Embedding planar graphs in four pages
- Algorithms for plane representations of acyclic digraphs
- The book thickness of a graph
- Graph minors. X: Obstructions to tree-decomposition
- Area requirement and symmetry display of planar upward drawings
- Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph
- Call routing and the ratcatcher
- Quasi-upward planarity
- On the pagenumber of complete bipartite graphs
- 1-page and 2-page drawings with bounded number of crossings per edge
- Arc diagrams, flip distances, and Hamiltonian triangulations
- Simpler algorithms for testing two-page book embedding of partitioned graphs
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Stack-number is not bounded by queue-number
- Planar graphs that need four pages
- Computing upward topological book embeddings of upward planar digraphs
- Advancements on SEFE and partitioned book embedding problems
- The book thickness of 1-planar graphs is constant
- Upward and quasi-upward planarity testing of embedded mixed graphs
- An analysis of some linear graph layout heuristics
- Book embeddability of series-parallel digraphs
- Recognizing DAGs with page-number 2 is NP-complete
- On the Computational Complexity of Upward and Rectilinear Planarity Testing
- Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs
- The 2-page crossing number of K n
- Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
- Linear-Size Universal Point Sets for One-Bend Drawings
- Upward Spirality and Upward Planarity Testing
- Upward Topological Book Embeddings of DAGs
- New upper bounds on the decomposability of planar graphs
- Unilateral Orientation of Mixed Graphs
- A Fully Dynamic Algorithm to Test the Upward Planarity of Single-Source Embedded Digraphs
- Crossing-Free Acyclic Hamiltonian Path Completion for Planar st-Digraphs
- Comparing Queues and Stacks As Machines for Laying Out Graphs
- Total Ordering Problem
- Stack and Queue Layouts of Directed Acyclic Graphs: Part I
- Stack and Queue Layouts of Directed Acyclic Graphs: Part II
- Graphs with E Edges Have Pagenumber O(√E)
- Genus g Graphs Have Pagenumber O(√g)
- Stack and Queue Layouts of Posets
- Optimal Upward Planarity Testing of Single-Source Digraphs
- Bounds For Orthogonal 3-D Graph Drawing
- Upward Partitioned Book Embeddings
- Planar L-Drawings of Directed Graphs
- Windrose Planarity
- Embedding Graphs into a Three Page Book with O(m log n) Crossings of Edges over the Spine
- On-Line Planarity Testing
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
- Dividing a Graph into Triconnected Components
- Implementing a Partitioned 2-Page Book Embedding Testing Algorithm
- On the Page Number of Upward Planar Directed Acyclic Graphs
- Planar L-Drawings of Bimodal Graphs
- Upward Book Embeddings of st-Graphs
- The complexity of colouring circle graphs
- Four pages are indeed necessary for planar graphs
- Intersection-Link Representations of Graphs
- Crossing minimization in linear embeddings of graphs
- Universal Point Sets for Drawing Planar Graphs with Circular Arcs
- ON EMBEDDING A GRAPH ON TWO SETS OF POINTS
- Extending upward planar graph drawings
- On dispersable book embeddings
- Edge partitions of optimal 2-plane and 3-plane graphs
- Greedy rectilinear drawings
- Upward planar morphs
- On the upward book thickness problem: combinatorial and complexity results
- The pagenumber of \(k\)-trees is \(O(k)\)
- A Sublinear Bound on the Page Number of Upward Planar Graphs
- Book embeddings of nonplanar graphs with small faces in few pages
- Recognizing DAGs with page-number 2 is NP-complete
This page was built for publication: Upward book embeddability of \(st\)-graphs: complexity and algorithms