Automorphism Groups of Geometrically Represented Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F15%3A10316698" target="_blank" >RIV/00216208:11320/15:10316698 - isvavai.cz</a>

Výsledek na webu

<a href="http://10.4230/LIPIcs.STACS.2015.540" target="_blank" >http://10.4230/LIPIcs.STACS.2015.540</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Automorphism Groups of Geometrically Represented Graphs

Popis výsledku v původním jazyce

Interval graphs are intersection graphs of closed intervals and circle graphs are intersection graphs of chords of a circle. We study automorphism groups of these graphs. We show that interval graphs have the same automorphism groups as trees, and circlegraphs have the same as pseudoforests, which are graphs with at most one cycle in every connected component. Our technique determines automorphism groups for classes with a strong structure of all geometric representations, and it can be applied to other graph classes. Our results imply polynomial-time algorithms for computing automorphism groups in term of group products.

Název v anglickém jazyce

Automorphism Groups of Geometrically Represented Graphs

Popis výsledku anglicky

Interval graphs are intersection graphs of closed intervals and circle graphs are intersection graphs of chords of a circle. We study automorphism groups of these graphs. We show that interval graphs have the same automorphism groups as trees, and circlegraphs have the same as pseudoforests, which are graphs with at most one cycle in every connected component. Our technique determines automorphism groups for classes with a strong structure of all geometric representations, and it can be applied to other graph classes. Our results imply polynomial-time algorithms for computing automorphism groups in term of group products.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

ISBN

978-3-939897-78-1

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

14

Strana od-do

540-553

Název nakladatele

Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

Místo vydání

Dagstuhl, Germany

Místo konání akce

Mnichov, Německo

Datum konání akce

4. 3. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—