Weakly Transitive Orientations, Hasse Diagrams and String Graphs

Middendorf, Matthias and Pfeiffer, Frank (1993) Weakly Transitive Orientations, Hasse Diagrams and String Graphs.
Published in: Discrete mathematics Vol. 111 (1-3). pp. 393-400.

Abstract

We introduce the notion of a weakly transitive orientation for graphs as a natural generalization of transitive orientations and give a characterization for weakly transitive orientations in terms of forbidden substructures. As a corollary of this characterization, we get that the Hasse diagrams of posets are exactly the triangle-free weakly transitive oriented graphs. Moreover, we characterize the complements of weakly transitive orientable graphs as a special class of intersection graphs of paths in planar graphs. In this way, complements of weakly transitive orientable graphs prove to form a common generalization of several known classes of intersection graphs such as circular-permutation graphs (and, thus, circular-arc graphs), complements of comparability graphs (and, thus, permutation graphs and interval graphs). An immediate consequence of this theorem is an intersection graph characterization of Hasse diagrams. Using this characterization, we obtain a simple reduction of the problem to decide for a graph whether it admits an orientation as a Hasse diagram to the recognition problem for string graphs. Using a result of Nesetril and Roedl that Hasse diagram orientation is NP-complete, this gives a new proof for NP-hardness of the string graph recognition problem. The status of complexity of the recognition problem for string graphs (intersection graphs of curves in the plane) was a long-standing open problem until J. Kratochvil gave a (rather involved) NP-hardness proof in 1988, see [J. Comb. Theory, Ser. B 52, No. 1, 67-78 (1991)].


Actions:
Full text not available from this repository.
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 2 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C75 Structural characterization of types of graphs

  • 05-XX Combinatorics > 05Cxx Graph theory > 05C99 None of the above, but in this section

  • Uncontrolled Keywords: characterization, circular-arc graphs, circular-permutation graphs, comparability graphs, complexity, Hasse diagrams, intersection graphs, interval graphs, NP-completeness, NP-hardness, permutation graphs, planar graphs, recognition problem, string graphs
    Subjects: 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R10 Graph theory
    05-XX Combinatorics > 05Cxx Graph theory > 05C75 Structural characterization of types of graphs
    05-XX Combinatorics > 05Cxx Graph theory > 05C99 None of the above, but in this section
    Divisions: Mathematical Institute
    Depositing User: Archive Admin
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 19 Jan 2012 11:31
    Deposit Information:
    ZAIK Number: [error in script]
    Depositing User: Archive Admin
    Date Deposited: 02 Apr 2001 00:00
    Last Modified: 19 Jan 2012 11:31
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/91