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

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Passau

Year

2024

Author dc:creator

• Stumpf, Peter Frederik

Contributors dc:contributor

• Rutter, Ignaz

• partial representation
• simultaneous representation
• sunflower representation

Statement dc:rights

• Creative Commons - CC BY - Namensnennung 4.0 International

Repository record source_url

https://opus4.kobv.de/opus4-uni-passau/frontdoor/index/index/docId/1520

OAI identifier oai:identifier

oai:kobv.de-opus4-uni-passau:1520