Approximation algorithms for minimizing edge crossings in radial drawings

DOI10.1007/s00453-009-9277-4zbMath1205.68514MaRDI QIDQ5961979

Hiroshi Nagamochi, Seok-Hee Hong

Publication date: 16 September 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9277-4

zbMATH Keywords

graph algorithm; approximation algorithm; graph drawing; crossing minimization; hierarchical drawing; layered drawing; level drawing; radial drawing

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge crossings in drawings of bipartite graphs
• Drawing graphs in two layers
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• Counting edge crossings in a 2-layered drawing
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• On Bipartite Drawings and the Linear Arrangement Problem
• Crossing Number is NP-Complete
• A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• Graph Drawing and Applications for Software and Knowledge Engineers
• Drawing Bipartite Graphs on Two Parallel Convex Curves
• Graph Drawing
• Drawing graphs. Methods and models