Interval graph representation with given interval and intersection lengths

DOI10.1016/j.jda.2015.05.011zbMath1336.05134OpenAlexW1624107519MaRDI QIDQ491160

Johannes Köbler, Sebastian Kuhnert, Osamu Watanabe

Publication date: 24 August 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2015.05.011

zbMATH Keywords

intersection graphinterval graphlinear timelogspaceconstrained graph representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Dimension of restricted classes of interval orders ⋮ Parameterized complexity of perfectly matched sets ⋮ Stick graphs with length constraints ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Overlaying a hypergraph with a graph with bounded maximum degree ⋮ On the isomorphism problem for Helly circular-arc graphs

Cites Work

• Unnamed Item
• Maintaining knowledge about temporal intervals
• Extending partial representations of proper and unit interval graphs
• On the calculation of transitive reduction-closure of orders
• Chronological orderings of interval graphs
• The method of forced enumeration for nondeterministic automata
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Linear-time recognition of circular-arc graphs
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Extending partial representations of interval graphs
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• Helly Circular-Arc Graph Isomorphism Is in Logspace
• Bounded Representations of Interval and Proper Interval Graphs
• The LBFS Structure and Recognition of Interval Graphs
• Simultaneous Interval Graphs
• Interval Graphs: Canonical Representations in Logspace
• Reasoning about temporal relations
• Undirected connectivity in log-space
• Nondeterministic Space is Closed under Complementation
• Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
• Realizing Interval Graphs with Size and Distance Constraints
• Constraint Satisfaction Problems on Intervals and Lengths
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Efficient Parallel Algorithms for Chordal Graphs
• Disconnectivity and Relative Positions in Simultaneous Embeddings