Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation

DOI10.1016/j.dam.2012.05.028zbMath1252.05152MaRDI QIDQ714020

Stefan Porschen, Ewald Speckenmeyer, Andreas Wotzlaw

Publication date: 19 October 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.05.028

zbMATH Keywords

combinatorial optimization; satisfiability; graph drawing; computational biology; planar embedding; crossing minimization; tanglegram; 2-CNF; level graph; mixed Horn formula

Mathematics Subject Classification ID

05C05: Trees

05C10: Planar graphs; geometric and topological aspects of graph theory

05C62: Graph representations (geometric and intersection representations, etc.)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

Ordered Level Planarity, Geodesic Planarity and Bi-Monotonicity, Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization, Beyond level planarity: cyclic, torus, and simultaneous level planarity, The importance of being proper, Crossing Minimization in Storyline Visualization, Beyond Level Planarity

Uses Software

• CPLEX
• Sat4j

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparing trees via crossing minimization
• Satisfiability of mixed Horn formulas
• On the linear-cost subtree-transfer distance between phylogenetic trees
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Edge crossings in drawings of bipartite graphs
• A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs
• Crossing Number is NP-Complete
• Drawing (Complete) Binary Tanglegrams
• Efficient Planarity Testing
• Drawing Binary Tanglegrams: An Experimental Evaluation
• Conflict-Driven Answer Set Enumeration