Complexity of diagrams

DOI10.1007/BF00340774MaRDI QIDQ1316621zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, Vojtěch Rödl

Publication date 16 February 1995

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00340774

zbMATH Keywords

covering relationdiagramfinite posetNP-completenessundirected graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A remark on covering graphs
• Combinatorial partitions of finite posets and lattices - Ramsey lattices
• Graph Theory and Probability
• On a Probabilistic Graph-Theoretical Method

Cited in

(21)

• Cover-incomparability graphs of posets
• Covering posets
• Reorientations of covering graphs
• Lattices contained in planar orders are planar
• Every triangle-free planar graph has a planar upward drawing
• On the complexity of diagram testing
• Constructing colorings for diagrams
• On edge transitivity of directed graphs
• The complexity of cover graph recognition for some varieties of finite lattices
• Tree-width and dimension
• Inversions, cuts, and orientations
• Orders with level diagrams
• Planar posets, dimension, breadth and the number of minimal elements
• Comparability graphs among cover-incomparability graphs
• $st$-Orientations with Few Transitive Edges
• Contact graphs of boxes with unidirectional contacts
• Weakly transitive orientations, Hasse diagrams and string graphs
• Enumerating orientations of ordered sets
• Efficient polynomial algorithms for distributive lattices
• On the complexity of cover-incomparability graphs of posets
• Diagrams, orientations, and varieties

This page was built for publication: Complexity of diagrams

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