Weakly transitive orientations, Hasse diagrams and string graphs

DOI10.1016/0012-365X(93)90176-TzbMath0782.05070MaRDI QIDQ686503

Frank Pfeiffer, Matthias Middendorf

Publication date: 20 December 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

complexitycharacterizationplanar graphsNP-completerecognition problemNP-hardnessinterval graphsintersection graphscomparability graphspermutation graphsstring graphscircular-arc graphsHasse diagramscircular-permutation 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)

Related Items (8)

Reconfiguring minimum dominating sets: the \(\gamma\)-graph of a tree ⋮ String graphs. I: The number of critical nonstring graphs is infinite ⋮ Order-Preserving 1-String Representations of Planar Graphs ⋮ Coloring Hasse diagrams and disjointness graphs of curves ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ Unnamed Item ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Hasse diagrams with large chromatic number

Cites Work

• Comparability graphs and intersection graphs
• Complexity of diagrams

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