ICE-TCS seminar: Steven Chaplick

Constrained Recognition Problems on Geometric Graph Classes

  • 21.5.2019, 12:10 - 13:00


ICE-TCS seminar #335

Date and time: Tuesday, 21 May 2019, 12:10-13:00
Location: Room M117
Speaker: Steven Chaplick (Universität Würzburg, Germany)

Title: Constrained Recognition Problems on Geometric Graph Classes

Abstract: Geometric representations of graphs are ubiquitous in computer science due to their capacity to conveniently model many problems arising from application domains. For a graph class C characterised by having a representation (e.g., an embedding on a surface or as an intersection graph of certain objects), there is a generalization of the recognition problem called the partial representation extension problem (RepExt). This is problem family is formalised as follows.

Problem: RepExt(C)
Instance: A graph G = (V, E) and a C-representation R' of a subset V' of V.
Question: Can R' be extended to a C-representation of G, i.e., does there exist a C-representation R of G such that R' ⊆ R?

This family of problems has received significant focus in the past 15 years due to its ability to naturally capture side constraints one wishes to enforce within a geometric representation. In this talk, we survey some results on this topic.

Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á eða með því að senda tölvupóst á netfangið:
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our or send an e-mail: