Orthogonal graph drawing with flexibility constraints

DOI10.1007/s00453-012-9705-8zbMath1303.05182OpenAlexW2087261591MaRDI QIDQ476441

Ignaz Rutter, Dorothea Wagner, Marcus Krug, Thomas Bläsius

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://publikationen.bibliothek.kit.edu/1000019793

zbMATH Keywords

planar graphsembeddingsorthogonal drawingbend minimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) 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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Orthogonal layout with optimal face complexity, HV-planarity: algorithms and complexity, Planar Embeddings with Small and Uniform Faces, Orthogonal Graph Drawing with Inflexible Edges, Universal slope sets for 1-bend planar drawings, Grid recognition: classical and parameterized computational perspectives, Sketched representations and orthogonal planarity of bounded treewidth graphs, On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings, Orthogonal graph drawing with inflexible edges, Orthogonal planarity testing of bounded treewidth graphs

Cites Work

• Unnamed Item
• Theoretical results on at most 1-bend embeddability of graphs
• A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid
• A better heuristic for orthogonal graph drawings
• An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid
• On-line maintenance of triconnected components with SPQR-trees
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Maximal Flow Through a Network
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Spirality and Optimal Orthogonal Drawings
• On-Line Planarity Testing
• Flow in Planar Graphs with Multiple Sources and Sinks
• Faster shortest-path algorithms for planar graphs