Circular representation problem on hypergraphs
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.
- On the problem of how to represent a graph taking into account an additional structure
- Circular-arc hypergraphs: rigidity via connectedness
- Graphs and digraphs represented by intervals and circular arcs
- scientific article; zbMATH DE number 638686
- Representation theorems for graphs whose vertex set is partially ordered
- A structure theorem for the consecutive 1's property
- Characterization problems for graphs, partially ordered sets, lattices, and families of sets
- Combinatorial Configurations
- scientific article; zbMATH DE number 3889566 (Why is no real title available?)
- scientific article; zbMATH DE number 3641484 (Why is no real title available?)
- Incidence matrices and interval graphs
- Structure theorems for some circular-arc graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Strong Perfect Graph Conjecture for Planar Graphs
- On the problem of how to represent a graph taking into account an additional structure
- Algorithmic aspects of intersection graphs and representation hypergraphs
- An approach to solving \(A^{k}=J-I\)
- Combinatorial optimisation and hierarchical classifications
- scientific article; zbMATH DE number 638686 (Why is no real title available?)
- An Optimal Algorithm for Strict Circular Seriation
- Circular-arc hypergraphs: rigidity via connectedness
- On the Shannon entropy of the number of vertices with zero in-degree in randomly oriented hypergraphs
- Cyclic orders
- A Simple and Optimal Algorithm for Strict Circular Seriation
- Intersection representations of matrices by subtrees and unicycles on graphs
This page was built for publication: Circular representation problem on hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799695)
