Simultaneous Representation of Proper and Unit Interval Graphs
Open Access
- 28 February 2025
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 87 (5) , 783-811
Abstract
In a confluence of combinatorics and geometry, simultaneous representations provide a way to realize combinatorial objects that share common structure. A standard case in the study of simultaneous representations is the sunflower case where all objects share the same common structure. While the recognition problem for general simultaneous interval graphs—the simultaneous version of arguably one of the most well-studied graph classes—is NP-complete, the complexity of the sunflower case for three or more simultaneous interval graphs is currently open. In this work we settle this question for proper interval graphs. We give an algorithm to recognize simultaneous proper interval graphs in linear time in the sunflower case where we allow any number of simultaneous graphs. Simultaneous unit interval graphs are much more ‘rigid’ and therefore have less freedom in their representation. We show they can be recognized in time $$\mathcal {O}(|V|\cdot |E|)$$ for any number of simultaneous graphs in the sunflower case where $$G=(V,E)$$ is the union of the simultaneous graphs. We further show that both recognition problems are in general NP-complete if the number of simultaneous graphs is not fixed. The restriction to the sunflower case is in this sense necessary.
Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (RU 1903/3-1, RU 1903/3-1, Research Training Group 2153)
- Universität Passau
This publication has 25 references indexed in Scilit:
- Extending partial representations of circle graphsJournal of Graph Theory, 2018
- Extending Partial Representations of Proper and Unit Interval GraphsAlgorithmica, 2016
- On Some $\mathcal{NP}$ -complete SEFE Problems2014
- Simultaneous Interval Graphs2010
- Simultaneous Geometric Graph Embeddings2008
- Simultaneous Graph Embeddings with Fixed Edges2006
- Graph Sandwich ProblemsJournal of Algorithms, 1995
- A linear-time algorithm for proper interval graph recognitionInformation Processing Letters, 1995
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular‐arc graphs, and nested interval graphsJournal of Graph Theory, 1982
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979