A satisfiability formulation of problems on level graphs

MaRDI QIDQ2741531zbMATH OpenFDO

Authors Ewald Speckenmeyer, Endre Boros, Peter L. Hammer, Alex Kogan, Kazuhisa Makino, Ondřej Čepek, Bert Randerath, Bruno Simeone

Publication date 24 September 2001

zbMATH Keywords

combinatorial embedding problemslevel graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• A satisfiability-based approach for embedding generalized tanglegrams on level graphs
• Level Planar Embedding in Linear Time
• The book embedding problem from a SAT-solving perspective
• The importance of being proper (in clustered-level planarity and T-level planarity)
• Nonserial dynamic programming formulations of satisfiability

Cites work

• Crossing Number is NP-Complete
• Hierarchies and planarity theory

Cited in

(9)

• Beyond level planarity
• A satisfiability-based approach for embedding generalized tanglegrams on level graphs
• On Some Aspects of Mixed Horn Formulas
• Practical Level Planarity Testing and Layout with Embedding Constraints
• scientific article; zbMATH DE number 7765366 (Why is no real title available?)
• Level planarity is more difficult than we thought (poster abstract)
• Partial and constrained level planarity
• Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation
• Satisfiability of mixed Horn formulas

This page was built for publication: A satisfiability formulation of problems on level graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2741531)