Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time

DOI10.1007/978-3-030-68766-3_34MaRDI QIDQ5014135zbMATH OpenOpenAlexFDO

Authors Walter Didimo, Michael Kaufmann, Giuseppe Liotta, Giacomo Ortali

Publication date 1 December 2021

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

series-parallel graphsorthogonal drawingsrectilinear planarity testing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the linearity of testing planarity of graphs
• A new approach to the linearity of testing planarity of graphs
• A linear-time algorithm for testing outer-1-planarity
• A linear-time algorithm for testing outer-1-planarity
• Testing Full Outer-2-planarity in Linear Time
• A linear-time algorithm for testing full outer-2-planarity
• On the computational complexity of upward and rectilinear planarity testing
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
• Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs
• Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time

Cites work

• scientific article; zbMATH DE number 2123122 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 1953108 (Why is no real title available?)
• scientific article; zbMATH DE number 1500675 (Why is no real title available?)
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs
• Accelerated bend minimization
• Graph Drawing
• Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
• No-bend orthogonal drawings and no-bend orthogonally convex drawings of planar graphs (extended abstract)
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
• Orthogonal Drawings of Plane Graphs Without Bends
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• Spirality and Optimal Orthogonal Drawings

Cited in

(9)

• Rectilinear Planarity of Partial 2-Trees
• Testing Full Outer-2-planarity in Linear Time
• Unit-length rectangular drawings of graphs
• Grid straight-line embeddings of trees with a minimum number of bends per path
• Unit-length rectangular drawings of graphs
• Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time
• Planar rectilinear drawings of outerplanar graphs in linear time
• Rectilinear planarity of partial 2-trees
• On the computational complexity of upward and rectilinear planarity testing

This page was built for publication: Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time

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