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.…


| 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): | Creative Commons - CC BY - Namensnennung 4.0 International |

