Title: A Satisfiability Formulation of Problems on Level Graphs

Authors: Endre Boros, Ondrej Cepek, Peter Hammer, Alex Kogan, Kazuhisa Makino, Bert Randerath, Bruno Simeone and Ewald Speckenmeyer 

Abstract:
In this note we present a formulation of two related combinatorial embedding problems concerning level graphs in terms of CNF-formulas. The first problem is known as level planar embedding and the second as crossing-minimization-problem.