2026-07-23T04:33:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18743 2024-03-06T11:02:37Z ddc:004 open_access

Simultaneous Representation of Interval Graphs in the Sunflower Case Rutter, Ignaz Stumpf, Peter Interval Graphs Sunflower Case Simultaneous Representation Recognition Geometric Intersection Graphs A simultaneous representation of (vertex-labeled) graphs G_1,… ,G_k consists of a (geometric) intersection representation R_i for each graph G_i such that each vertex v is represented by the same geometric object in each R_i for which G_i contains v. While Jampani and Lubiw showed that the existence of simultaneous interval representations for k = 2 can be tested efficiently (2010), testing it for graphs where k is part of the input is NP-complete (Bok and Jedličková, 2018). An important special case of simultaneous representations is the sunflower case, where G_i ∩ G_j = (V(G_i)∩ V(G_j),E(G_i)∩ E(G_j)) is the same graph for each i ≠ j. We give an O(∑_{i=1}^k (|V(G_i)|+|E(G_i)|))-time algorithm for deciding the existence of a simultaneous interval representation for the sunflower case, even when k is part of the input. This answers an open question of Jampani and Lubiw. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ignaz Rutter and Peter Stumpf 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.90 urn:nbn:de:0030-drops-187435 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.90 eng https://creativecommons.org/licenses/by/4.0/legalcode