License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.90
URN: urn:nbn:de:0030-drops-187435
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18743/
Go to the corresponding LIPIcs Volume Portal

Rutter, Ignaz ; Stumpf, Peter

Simultaneous Representation of Interval Graphs in the Sunflower Case

pdf-format:
LIPIcs-ESA-2023-90.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{rutter_et_al:LIPIcs.ESA.2023.90,
  author =	{Rutter, Ignaz and Stumpf, Peter},
  title =	{{Simultaneous Representation of Interval Graphs in the Sunflower Case}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{90:1--90:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18743},
  URN =		{urn:nbn:de:0030-drops-187435},
  doi =		{10.4230/LIPIcs.ESA.2023.90},
  annote =	{Keywords: Interval Graphs, Sunflower Case, Simultaneous Representation, Recognition, Geometric Intersection Graphs}
}

Keywords: Interval Graphs, Sunflower Case, Simultaneous Representation, Recognition, Geometric Intersection Graphs
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI