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.
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr90-091
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