k-Level Crossing Minimization Is NP-Hard for Trees

DOI10.1007/978-3-642-19094-0_9zbMath1317.68057OpenAlexW169943627MaRDI QIDQ3078383

Martin Harrigan, Patrick Healy

Publication date: 20 February 2011

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_9

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On optimal linear arrangements of trees
• Edge crossings in drawings of bipartite graphs
• On Bipartite Drawings and the Linear Arrangement Problem
• Crossing Number is NP-Complete
• Multi-Terminal 0–1 Flow
• Breaking cycles for minimizing crossings

This page was built for publication: k-Level Crossing Minimization Is NP-Hard for Trees