A satisfiability formulation of problems on level graphs

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

Research output: Contribution to journalArticle

11 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)269-277
Number of pages9
JournalElectronic Notes in Discrete Mathematics
StatePublished - Jan 1 2001

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


  • 2CNF, level graphs
  • Level-planar, crossing-minimization
  • Satisfiability

Fingerprint Dive into the research topics of 'A satisfiability formulation of problems on level graphs'. Together they form a unique fingerprint.

  • Cite this

    Randerath, B., Speckenmeyer, E., Boros, E., Hammer, P., Kogan, A., Makino, K., Simeone, B., & Cepek, O. (2001). A satisfiability formulation of problems on level graphs. Electronic Notes in Discrete Mathematics, 9, 269-277. https://doi.org/10.1016/S1571-0653(04)00327-0