Drawing (complete) binary tanglegrams

DOI10.1007/s00453-010-9456-3zbMath1236.68079OpenAlexW2123192541MaRDI QIDQ2428677

Alexander Wolff, Martin Nöllenburg, Maike Buchin, Jaroslaw Byrka, Kevin Buchin, Yoshio Okamoto, Rodrigo I. Silveira

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9456-3

zbMATH Keywords

approximation algorithmNP-hardnesscrossing minimizationfixed-parameter tractabilitybinary tanglegram

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) Approximation algorithms (68W25)

Related Items (15)

The shape of random tanglegrams ⋮ Analogies between the crossing number and the tangle crossing number ⋮ An infinite antichain of planar tanglegrams ⋮ Some problems related to the space of optimal tree reconciliations (invited talk) ⋮ On the enumeration of tanglegrams and tangled chains ⋮ Unnamed Item ⋮ Planar tanglegram layouts and single edge insertion ⋮ Sampling planar tanglegrams and pairs of disjoint triangulations ⋮ Crossing Minimization in Storyline Visualization ⋮ Visualizing multispecies coalescent trees: drawing gene trees inside species trees ⋮ On the 2-layer window width minimization problem ⋮ Block crossings in one-sided tanglegrams ⋮ The largest crossing number of tanglegrams ⋮ Visualizing co-phylogenetic reconciliations ⋮ A new non-Archimedean metric on persistent homology

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simplified NP-complete MAXSAT problem
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Edge crossings in drawings of bipartite graphs
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• A projected gradient algorithm for solving the maxcut SDP relaxation
• On the power of unique 2-prover 1-round games
• Drawing (Complete) Binary Tanglegrams
• A Faster Fixed-Parameter Approach to Drawing Binary Tanglegrams
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Optimal Upward Planarity Testing of Single-Source Digraphs
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: Drawing (complete) binary tanglegrams