Simultaneous representation of proper and unit interval graphs

DOI10.1007/S00453-025-01296-XMaRDI QIDQ6980431zbMATH OpenFDO

Authors Ignaz Rutter, Darren Strash, Peter Stumpf, Michael Vollmer

Publication date 22 May 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-025-01296-X

zbMATH Keywords

proper interval graphsrecognitionunit interval graphsgeometric intersection graphssimultaneous representation

Mathematics Subject Classification ID

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

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A linear-time algorithm for proper interval graph recognition
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Algorithmic graph theory and perfect graphs
• Efficient graph representations
• Extending partial representations of circle graphs
• Extending partial representations of proper and unit interval graphs
• Graph Sandwich Problems
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time recognition of probe interval graphs
• On Some $\mathcal{NP}$ -complete SEFE Problems
• On simultaneous planar graph embeddings
• Optimal greedy algorithms for indifference graphs
• Recognition of probe proper interval graphs
• Simultaneous Geometric Graph Embeddings
• Simultaneous Graph Embeddings with Fixed Edges
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Simultaneous interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The simultaneous representation problem for chordal, comparability and permutation graphs
• Total Ordering Problem
• Toward a theory of planarity: Hanani-Tutte and planarity variants

This page was built for publication: Simultaneous representation of proper and unit interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6980431)