Technical Report CS0385

Title: Acyclic Hypergraph Projections and Relationships to Cirrcular-Arc Graphs
Authors: Aviv Lustig and Oded Shmueli
Abstract: Hypergraphs can be partitioned into two classes: tree (aqyclic) hypergraphs and cyclic hypergraphs . This paper analyzes a new class of cyclic hypergraphs called Xrings. Hypergraph H is an Xring if the edges of H can be circulary ordered so that for every vertex, all edges containing the vertex are consecutive; in addition no edge may be a subset of another eage and no vertex may appear in exactly one edge. Let H1 and H2 be two hypergraphs. A tree projectipn is a tree hypergraph H3 such that each edge in H1 is contained in some edge of H2 and each edge in H3 is contained in some edge of H2. A polynomial time algorithm is presented for deciding, given Xring H1 and arbitrary hypergraph H2, whether there exists a tree projection. It is shown that hypergraph H is an Xring iff a modified adjacency graph of H is a circular-arc graph. Finally, relationships between Xrings and circular representable hypergraphs are investigated.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1985
To the main CS technical reports page

Computer science department, Technion