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

Speckenmeyer, Ewald and Wotzlaw, Andreas and Porschen, Stefan (2011) A Satisfiability-based Approach for Embedding Generalized Tanglegrams on Level Graphs.
Published In: Theory and Applications of Satisfiability Testing - SAT 2011 : 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011. Proceedings, Lecture notes in computer science. 6695 Springer February 2011, pp. 134-144.

Abstract

A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in computational biology to compare evolutionary histories of species. In this paper we present a formulation of two related combinatorial embedding problems concerning tanglegrams in terms of CNF-formulas. The first problem is known as planar embedding and the second as crossing minimization problem. We show that our satisfiability formulation of these problems can handle a much more general case with more than two, not necessarily binary or complete, trees defined on arbitrary sets of leaves and allowed to vary their layouts.


Actions:
Download: [img] PDF - Preprinted Version
Download (299kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2011-614
Depositing User: Andreas Wotzlaw
Date Deposited: 23 Feb 2011 00:00
Last Modified: 09 Jan 2012 12:06
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/614