Comparing trees via crossing minimization

DOI10.1016/j.jcss.2009.10.014zbMath1210.05023OpenAlexW2077946037MaRDI QIDQ988574

Henning Fernau, Mathias Poths, Michael Kaufmann

Publication date: 18 August 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.10.014

zbMATH Keywords

crossing minimizationparameterized algorithmsdrawing tanglegrams

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

An infinite antichain of planar tanglegrams ⋮ Planar tanglegram layouts and single edge insertion ⋮ Characterizing planar tanglegram layouts and applications to edge insertion problems ⋮ 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 ⋮ A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs ⋮ Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization ⋮ Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation ⋮ Visualizing co-phylogenetic reconciliations ⋮ A new non-Archimedean metric on persistent homology ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey on tree edit distance and related problems
• Alignment of trees -- an alternative to tree edit
• Fixed parameter algorithms for one-sided crossing minimization revisited
• Bioinformatics and computational biology. First international conference, BICoB 2009, New Orleans, LA, USA, April 8--10, 2009. Proceedings
• Edge crossings in drawings of bipartite graphs
• Drawing graphs in two layers
• A efficient fixed parameter tractable algorithm for 1-sided crossing minimzation
• A fixed-parameter approach to 2-layer planarization
• Constructing Optimal Trees from Quartets
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Simple and Efficient Bilayer Cross Counting
• Two-Layer Planarization: Improving on Parameterized Algorithmics
• Drawing (Complete) Binary Tanglegrams
• Algorithms on Strings, Trees and Sequences
• Nonlinear pattern matching in trees
• Optimal Upward Planarity Testing of Single-Source Digraphs
• Ordered and Unordered Tree Inclusion
• Drawing Binary Tanglegrams: An Experimental Evaluation

This page was built for publication: Comparing trees via crossing minimization