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

geometric intersection graphsproper interval graphsrecognitionsimultaneous representationunit interval graphs

Mathematics Subject Classification ID

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

Cites work

• 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
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Linear-time recognition of probe interval graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• On simultaneous planar graph embeddings
• On Some $\mathcal{NP}$ -complete SEFE Problems
• Optimal greedy algorithms for indifference graphs
• Recognition of probe proper interval graphs
• Simultaneous Geometric Graph Embeddings
• Simultaneous Graph Embeddings with Fixed Edges
• Simultaneous interval graphs
• Simultaneous PQ-ordering with applications to constrained embedding problems
• 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

Cited in

(1)

• Structural parameterizations of simultaneous planarity

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)