@inproceedings{6a4fc556ec00419489c7e8419c21258f,

title = "Drawing (complete) binary tanglegrams: hardness, approximation, fixed-parameter tractability",

abstract = "A binary tanglegram is a pair of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn without edge crossings and that the inter-tree edges have as few crossings as possible. It is known that finding a drawing with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We prove that under the Unique Games Conjecture there is no constant-factor approximation for general binary trees. We show that the problem is hard even if both trees are complete binary trees. For this case we give an O(n 3)-time 2-approximation and a new and simple fixed-parameter algorithm. We show that the maximization version of the dual problem for general binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.",

author = "K. Buchin and M. Buchin and J. Byrka and M. N{\"o}llenburg and Y. Okamoto and R.I. Silveira and A. Wolff",

year = "2009",

doi = "10.1007/978-3-642-00219-9_32",

language = "English",

isbn = "978-3-642-00218-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "324--335",

editor = "I.G. Tollis and M. Patrignani",

booktitle = "Graph Drawing (16th International Symposium, GD'08, Heraklion, Crete, Greece, September 21-24, 2008, Revised Papers)",

address = "Germany",

}