Accelerated Bend Minimization

DOI10.1007/978-3-642-25878-7_12zbMath1311.68109OpenAlexW2166620307MaRDI QIDQ5895514

Andreas Karrenbauer, Sabine Cornelsen

Publication date: 9 March 2012

Published in: Graph Drawing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-25878-7_12

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Flows in graphs (05C21)

Related Items

On orthogonally convex drawings of plane graphs, A topology-shape-metrics framework for ortho-radial graph drawing, An annotated review on graph drawing and its applications, Sliding column model for t-unit bar visibility representations of graphs, Bend-optimal orthogonal drawings of triconnected plane graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A new polynomial-time algorithm for linear programming
• Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
• Finding small simple cycle separators for 2-connected planar graphs
• A better heuristic for orthogonal graph drawings
• Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• How to draw the minimum cuts of a planar graph
• Planar graphs, negative weight edges, shortest paths, and near linear time
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
• Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Flow in Planar Graphs with Multiple Sources and Sinks
• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
• Graph Drawing
• Faster shortest-path algorithms for planar graphs