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

DOI10.1007/978-3-030-68766-3_34OpenAlexW3134933682MaRDI QIDQ5014135

Giacomo Ortali, Michael Kaufmann, Giuseppe Liotta, Walter Didimo

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)

Related Items (6)

Planar rectilinear drawings of outerplanar graphs in linear time ⋮ Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time ⋮ Unit-length rectangular drawings of graphs ⋮ Rectilinear planarity of partial 2-trees ⋮ Rectilinear Planarity of Partial 2-Trees ⋮ Grid straight-line embeddings of trees with a minimum number of bends per path

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sketched representations and orthogonal planarity of bounded treewidth graphs
• 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
• Spirality and Optimal Orthogonal Drawings
• A Linear Algorithm for Bend-Optimal Orthogonal Drawings of Triconnected Cubic Plane Graphs
• Orthogonal Drawings of Plane Graphs Without Bends
• Optimal Orthogonal Drawings of Planar 3-Graphs in Linear Time
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Accelerated Bend Minimization
• Graph Drawing

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