Orthogonal graph drawing with inflexible edges

DOI10.1016/j.comgeo.2016.03.001zbMath1384.05115OpenAlexW2298171962MaRDI QIDQ679739

Ignaz Rutter, Thomas Bläsius, Sebastian B. C. Lehmann

Publication date: 19 January 2018

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2016.03.001

zbMATH Keywords

computational complexityplanar embeddingparameterized algorithmbend minimizationorthgonal graph drawing

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (15)

Planar rectilinear drawings of outerplanar graphs in linear time ⋮ HV-planarity: algorithms and complexity ⋮ Extending Partial Orthogonal Drawings ⋮ Universal slope sets for 1-bend planar drawings ⋮ A topology-shape-metrics framework for ortho-radial graph drawing ⋮ Optimal morphs of planar orthogonal drawings. II ⋮ Sketched representations and orthogonal planarity of bounded treewidth graphs ⋮ An SPQR-tree-like embedding representation for upward planarity ⋮ On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings ⋮ Unnamed Item ⋮ Approximation Algorithms for Facial Cycles in Planar Embeddings ⋮ Orthogonal planarity testing of bounded treewidth graphs ⋮ An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings ⋮ Extending Partial Orthogonal Drawings ⋮ Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time

Cites Work

• Unnamed Item
• Orthogonal graph drawing with flexibility constraints
• A better heuristic for orthogonal graph drawings
• On-line maintenance of triconnected components with SPQR-trees
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Spirality and Optimal Orthogonal Drawings
• On-Line Planarity Testing
• Optimal Orthogonal Graph Drawing with Convex Bend Costs
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Accelerated Bend Minimization

This page was built for publication: Orthogonal graph drawing with inflexible edges