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.
- Title
- A Satisfiability Formulation of Problems on Level Graphs
- Creators
- Bert Randerath - Institut für Informatik, Universitat zu Köln, D-50969, Köln, GermanyEwald Speckenmeyer - Institut für Informatik, Universitat zu Köln, D-50969, Köln, GermanyEndre Boros - RUTCOR, Rutgers University, Piscataway, NJ 08854-8003, USAPeter Hammer - RUTCOR, Rutgers University, Piscataway, NJ 08854-8003, USAAlex Kogan - RUTCOR, Rutgers University, Piscataway, NJ 08854-8003, USAKazuhisa Makino - Department of Systems and Human Science, Graduate School of Engineering Science, Osaka University, Toyonaka, Osaka, 560-8531, JapanBruno Simeone - Dipartimento di Statistica, Probabilita e Statische Applicate, Universita La Sapienza, Roma, ItalyOndrej Cepek - Department of Theoretical Computer Science and Mathematical Logic, Charles University, Malostranske nam. 25, 118 00, Prague 1, Czech Republic
- Publication Details
- Electronic notes in discrete mathematics, Vol.9, pp.269-277
- Date published
- 2001
- Publisher
- Elsevier B.V
- Academic Unit
- Management Science and Information Systems (RBS)
- Language
- English
- Resource Type
- Journal article
- Identifiers
- 991031666252604646