Weakly transitive orientations, Hasse diagrams and string graphs

DOI10.1016/0012-365X(93)90176-TMaRDI QIDQ686503zbMATH OpenFDO

Authors Matthias Middendorf, Frank Pfeiffer

Publication date 20 December 1993

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexityintersection graphsinterval graphscharacterizationcircular-arc graphsNP-completeNP-hardnessplanar graphsrecognition problempermutation graphscomparability graphsHasse diagramscircular-permutation graphsstring graphsweakly transitive orientable graphsweakly transitive orientation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Recommendations

• scientific article; zbMATH DE number 3939387
• String graphs and incomparability graphs
• String graphs and incomparability graphs
• Transitive Orientations of Graphs
• On weakly half-transitive graphs
• On transitive orientations with restricted covering graphs
• Weakly Hadamard diagonalizable graphs
• Strongly 2-connected orientations of graphs
• On the Structure of the Strong Orientations of a Graph
• Semi-transitive orientations and word-representable graphs

Cites work

• Comparability graphs and intersection graphs
• Complexity of diagrams

Cited in

(8)

• Computing maximum independent set on outerstring graphs and their relatives
• String graphs. I: The number of critical nonstring graphs is infinite
• Order-preserving 1-string representations of planar graphs
• Hasse diagrams with large chromatic number
• Reconfiguring minimum dominating sets: the -graph of a tree
• On the size of outer-string representations
• Outerstring graphs are \(\chi \)-bounded
• Coloring Hasse diagrams and disjointness graphs of curves

This page was built for publication: Weakly transitive orientations, Hasse diagrams and string graphs

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