KIT | KIT-Bibliothek | Impressum | Datenschutz

Extending Partial Representations of Circle Graphs in Near-Linear Time

Brückner, Guido 1; Rutter, Ignaz; Stumpf, Peter
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph H ⊆ G and a representation H of H. The question is whether G admits a representation G whose restriction to H is H. We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams. We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in O((n+m)α(n+m)) time, where α is the inverse Ackermann function. This improves over an O(n$^{3}$)-time algorithm by Chaplick, Fulek and Klavík [2019]. The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.


Verlagsausgabe §
DOI: 10.5445/IR/1000151221
Veröffentlicht am 06.10.2022
Originalveröffentlichung
DOI: 10.4230/LIPIcs.MFCS.2022.25
Scopus
Zitationen: 1
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2022
Sprache Englisch
Identifikator ISBN: 978-3-9597725-6-3
ISSN: 1868-8969
KITopen-ID: 1000151221
Erschienen in 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Ed.: Stefan Szeider
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.Nr. 25
Serie LIPIcs - Leibniz International Proceedings in Informatics ; 241
Nachgewiesen in Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page