Partial Representation Extension and Simultaneous Representation of Intersection Graphs

  • Many real world problems can be modeled with geometric intersection graphs. A (geometric) intersection representation of a graph G=(V,E) is a family {R_v}_{v\in V} of geometric objects such that two geometric objects R_u, R_v intersect if and only if the corresponding vertices u, v are adjacent in G. The most prominent class of intersection graphs are interval graphs, which have representations consisting only of intervals on the real line. Interval graphs have applications in genetics, scheduling, archaeology and many more fields. The recognition problem asks the question whether a given graph belongs to a certain graph class. Two natural generalizations of the recognition problem are the partial representation extension problem and the simultaneous representation problem. In the partial representation extension problem one is given a graph G and a partial representation, i.e., a representation of a subgraph of G. The question then is whether the partial representation can be extended to the whole graph G without changing theMany real world problems can be modeled with geometric intersection graphs. A (geometric) intersection representation of a graph G=(V,E) is a family {R_v}_{v\in V} of geometric objects such that two geometric objects R_u, R_v intersect if and only if the corresponding vertices u, v are adjacent in G. The most prominent class of intersection graphs are interval graphs, which have representations consisting only of intervals on the real line. Interval graphs have applications in genetics, scheduling, archaeology and many more fields. The recognition problem asks the question whether a given graph belongs to a certain graph class. Two natural generalizations of the recognition problem are the partial representation extension problem and the simultaneous representation problem. In the partial representation extension problem one is given a graph G and a partial representation, i.e., a representation of a subgraph of G. The question then is whether the partial representation can be extended to the whole graph G without changing the given partial representation. In the simultaneous representation problem one is given multiple graphs G_1,...,G_k that can have shared parts, and the question is whether there are representations of all input graphs such that shared vertices are represented by the same geometric objects. Often the sunflower case is considered, where the shared part of any two input graphs is the same. We determine the complexity of the partial representation extension problem and the simultaneous representation problem, especially in the sunflower case for various intersection graph classes. We also improve the running time for various intersection graph classes. In particular, we show that the partial representation extension problem for circular-arc graphs is NP-complete and that the simultaneous representation problem for interval graphs can be solved in linear time in the sunflower case, answering open questions from 2014 and 2010.show moreshow less

Download full text files

Export metadata

Metadaten
Author:Peter Frederik StumpfORCiD
URN:urn:nbn:de:bvb:739-opus4-15201
Advisor:Ignaz Rutter
Document Type:Doctoral Thesis
Language:English
Year of Completion:2024
Date of Publication (online):2024/12/19
Date of first Publication:2024/12/19
Publishing Institution:Universität Passau
Granting Institution:Universität Passau, Fakultät für Informatik und Mathematik
Date of final exam:2024/01/10
Release Date:2024/12/19
Tag:partial representation; simultaneous representation; sunflower representation
Page Number:IX, 208 Seiten
Institutes:Fakultät für Informatik und Mathematik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
open_access (DINI-Set):open_access
Licence (German):License LogoCreative Commons - CC BY - Namensnennung 4.0 International