TY - GEN
T1 - k-level crossing minimization is NP-hard for trees
AU - Harrigan, Martin
AU - Healy, Patrick
PY - 2011
Y1 - 2011
N2 - The k-level crossing minimization problem for graphs has received much interest in the graph drawing literature. In this paper we focus on the special case of trees. We show that the 2-level crossing minimization problem for trees where the order of the vertices on one level is fixed is solvable in quadratic time. We also show that the k-level crossing minimization problem for trees for an arbitrary number of levels is NP-Hard. This result exposes a source of difficulty for algorithm designers that compounds earlier results relating to the 2-level crossing minimization problem for graphs.
AB - The k-level crossing minimization problem for graphs has received much interest in the graph drawing literature. In this paper we focus on the special case of trees. We show that the 2-level crossing minimization problem for trees where the order of the vertices on one level is fixed is solvable in quadratic time. We also show that the k-level crossing minimization problem for trees for an arbitrary number of levels is NP-Hard. This result exposes a source of difficulty for algorithm designers that compounds earlier results relating to the 2-level crossing minimization problem for graphs.
UR - http://www.scopus.com/inward/record.url?scp=79952275927&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-19094-0_9
DO - 10.1007/978-3-642-19094-0_9
M3 - Conference contribution
AN - SCOPUS:79952275927
SN - 9783642190933
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 70
EP - 76
BT - WALCOM
T2 - 5th Annual Workshop on Algorithms and Computation, WALCOM 2011
Y2 - 18 February 2011 through 20 February 2011
ER -