Circular-arc hypergraphs: rigidity via connectedness

DOI10.1016/J.DAM.2016.08.008zbMath1358.05204arXiv1312.1172OpenAlexW2396285612MaRDI QIDQ516817

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.1172

zbMATH Keywords

intersection graphscircular-ones propertycircular-arc hypergraphsgraph canonizationproper circular-arc graphsunique representations

Mathematics Subject Classification ID

Hypergraphs (05C65) Connectivity (05C40)

Related Items (2)

An Optimal Algorithm for Strict Circular Seriation ⋮ Cyclic arrangements with minimum modulo \(m\) winding numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Circular representation problem on hypergraphs
• Intersection representations of matrices by subtrees and unicycles on graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Interval hypergraphs and D-interval hypergraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• PC trees and circular-ones arrangements.
• On the structure of local tournaments
• Fully dynamic recognition of proper circular-arc graphs
• On the compatibility between a graph and a simple order
• Matrix characterizations of circular-arc graphs
• Interval Graphs: Canonical Representations in Logspace
• A Simple Test for the Consecutive Ones Property
• Parallel recognition of the consecutive ones property with applications
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Convex-Round and Concave-Round Graphs
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Neighborhood hypergraphs of bipartite graphs

This page was built for publication: Circular-arc hypergraphs: rigidity via connectedness