A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs

DOI10.1007/978-3-642-21581-0_12zbMath1330.68225OpenAlexW88002070MaRDI QIDQ3007679

Andreas Wotzlaw, Stefan Porschen, Ewald Speckenmeyer

Publication date: 17 June 2011

Published in: Theory and Applications of Satisfiability Testing - SAT 2011 (Search for Journal in Brave)

Full work available at URL: http://e-archive.informatik.uni-koeln.de/614/2/zaik2011-614.pdf

zbMATH Keywords

satisfiabilitygraph drawingplanar embeddingcrossing minimizationtanglegram2-CNFlevel graphmixed Horn formula

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• Crossing Number is NP-Complete
• Drawing (Complete) Binary Tanglegrams
• Efficient Planarity Testing