KIT | KIT-Bibliothek | Impressum | Datenschutz

Simultaneous Representation of Proper and Unit Interval Graphs

Rutter, Ignaz; Strash, Darren; Stumpf, Peter ; Vollmer, Michael 1,2
1 Fakultät für Informatik (INFORMATIK), Karlsruher Institut für Technologie (KIT)
2 Karlsruher Institut für Technologie (KIT)

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 O(|V | · |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
... mehr


Verlagsausgabe §
DOI: 10.5445/IR/1000179878
Veröffentlicht am 10.03.2025
Cover der Publikation
Zugehörige Institution(en) am KIT Fakultät für Informatik (INFORMATIK)
Publikationstyp Zeitschriftenaufsatz
Publikationsmonat/-jahr 05.2025
Sprache Englisch
Identifikator ISSN: 0178-4617, 1432-0541
KITopen-ID: 1000179878
Erschienen in Algorithmica
Verlag Springer
Band 87
Heft 5
Seiten 783–811
Vorab online veröffentlicht am 28.02.2025
Nachgewiesen in Web of Science
Scopus
OpenAlex
Dimensions
KIT – Die Universität in der Helmholtz-Gemeinschaft
KITopen Landing Page