Circular representation problem on hypergraphs
type: Item
instance of: scholarly article
title: Circular representation problem on hypergraphs
zbMATH Open document ID: 0548.05047
DOI: 10.1016/0012-365X(84)90006-2
published in: Discrete Mathematics
publication date: 1984-01-01T00:00:00Z
review text: A hypergraph (V,E) is called circular-representable if there exists a bijection from the vertex set into a topological circle such that the vertices of every edge determine an interval with respect to the circular order at the circle (i.e. they are consecutive points on the circle). Necessary and sufficient conditions for the circular representability of a hypergraph are proved. Those circular-representable hypergraphs with a unique cicular representation (up to symmetries of the circle) are characterized. A group of transformations is constructed which acts transitively on the set of all circular representations of a hypergraph; this gives a theoretical overview over all different representations. This is applied to obtain a similar result for interval-representable hypergraphs (which are definded by the corresponding property for the line). Finally relations to the problem of characterizing circular graphs are established: With graphs G of a restricted class of graphs, a hypergraph H(G) is associated in a certain way such that G is circular iff H(G) is circular representable.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 3873376
zbMATH Keywords: circular representation
zbMATH Keywords: interval-representable hypergraphs
zbMATH Keywords: circular graphs
author: Alain Quilliot
MaRDI profile type: Publication
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Q4200096
cites work: Q3222876
cites work: Incidence matrices and interval graphs
cites work: Combinatorial Configurations
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
cites work: A structure theorem for the consecutive 1's property
cites work: The Strong Perfect Graph Conjecture for Planar Graphs
cites work: Structure theorems for some circular-arc graphs
description: scientific article; zbMATH DE number 3873376