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

DOI10.1016/j.dam.2012.05.028zbMath1252.05152OpenAlexW2108601082MaRDI 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 optimizationsatisfiabilitygraph drawingcomputational biologyplanar embeddingcrossing minimizationtanglegram2-CNFlevel graphmixed Horn formula

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Crossing Minimization in Storyline Visualization ⋮ Beyond Level Planarity ⋮ 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

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

This page was built for publication: Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation