Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks

Mikkel Abrahamsen; Bartosz Walczak

doi:10.4230/LIPIcs.SoCG.2023.2

Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks

Mikkel Abrahamsen^*, Bartosz Walczak

^*Corresponding author af dette arbejde

Algorithms and Complexity

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

11 Downloads (Pure)

Abstract

For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes G^hom(A) and G^sim(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that G^hom(A) = G^hom(B) if and only if A and B are affine equivalent, and G^sim(A) = G^sim(B) if and only if A and B are similar.

Originalsprog	Engelsk
Titel	39th International Symposium on Computational Geometry, SoCG 2023
Redaktører	Erin W. Chambers, Joachim Gudmundsson
Forlag	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Publikationsdato	2023
Sider	1-16
Artikelnummer	2
ISBN (Elektronisk)	9783959772730
DOI	https://doi.org/10.4230/LIPIcs.SoCG.2023.2
Status	Udgivet - 2023
Begivenhed	39th International Symposium on Computational Geometry, SoCG 2023 - Dallas, USA Varighed: 12 jun. 2023 → 15 jun. 2023

Konference

Konference	39th International Symposium on Computational Geometry, SoCG 2023
Land/Område	USA
By	Dallas
Periode	12/06/2023 → 15/06/2023

Navn	Leibniz International Proceedings in Informatics, LIPIcs
Vol/bind	258
ISSN	1868-8969

Bibliografisk note

Funding Information:
Funding Mikkel Abrahamsen: The author is supported by Starting Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere Aude research career programme. BARC is supported by the VILLUM Foundation grant 16582. Bartosz Walczak: The author is partially supported by the National Science Center of Poland grant 2015/17/D/ST1/00585.

Publisher Copyright:
© Mikkel Abrahamsen and Bartosz Walczak; licensed under Creative Commons License CC-BY 4.0.

Adgang til dokumentet

10.4230/LIPIcs.SoCG.2023.2Licens: CC BY

FulltextForlagets udgivne version, 1,42 MBLicens: CC BY

Citationsformater

Abrahamsen, M., & Walczak, B. (2023). Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. I E. W. Chambers, & J. Gudmundsson (red.), 39th International Symposium on Computational Geometry, SoCG 2023 (s. 1-16). [2] Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Leibniz International Proceedings in Informatics, LIPIcs Bind 258 https://doi.org/10.4230/LIPIcs.SoCG.2023.2

Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. / Abrahamsen, Mikkel; Walczak, Bartosz.

39th International Symposium on Computational Geometry, SoCG 2023. red. / Erin W. Chambers; Joachim Gudmundsson. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. s. 1-16 2 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Abrahamsen, M & Walczak, B 2023, Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. i EW Chambers & J Gudmundsson (red), 39th International Symposium on Computational Geometry, SoCG 2023., 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics, LIPIcs, bind 258, s. 1-16, 39th International Symposium on Computational Geometry, SoCG 2023, Dallas, USA, 12/06/2023. https://doi.org/10.4230/LIPIcs.SoCG.2023.2

Abrahamsen M, Walczak B. Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. I Chambers EW, Gudmundsson J, red., 39th International Symposium on Computational Geometry, SoCG 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. s. 1-16. 2. (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258). https://doi.org/10.4230/LIPIcs.SoCG.2023.2

Abrahamsen, Mikkel ; Walczak, Bartosz. / Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks. 39th International Symposium on Computational Geometry, SoCG 2023. red. / Erin W. Chambers ; Joachim Gudmundsson. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. s. 1-16 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 258).

@inproceedings{ec720b6ab5a94ce29d3c97564a184dac,

title = "Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks",

abstract = "For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes Ghom(A) and Gsim(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that Ghom(A) = Ghom(B) if and only if A and B are affine equivalent, and Gsim(A) = Gsim(B) if and only if A and B are similar.",

keywords = "convex disk, geometric intersection graph, homothet, similarity",

author = "Mikkel Abrahamsen and Bartosz Walczak",

note = "Publisher Copyright: {\textcopyright} Mikkel Abrahamsen and Bartosz Walczak; licensed under Creative Commons License CC-BY 4.0.; 39th International Symposium on Computational Geometry, SoCG 2023 ; Conference date: 12-06-2023 Through 15-06-2023",

year = "2023",

doi = "10.4230/LIPIcs.SoCG.2023.2",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--16",

editor = "Chambers, {Erin W.} and Joachim Gudmundsson",

booktitle = "39th International Symposium on Computational Geometry, SoCG 2023",

}

TY - GEN

T1 - Distinguishing Classes of Intersection Graphs of Homothets or Similarities of Two Convex Disks

AU - Abrahamsen, Mikkel

AU - Walczak, Bartosz

N1 - Publisher Copyright: © Mikkel Abrahamsen and Bartosz Walczak; licensed under Creative Commons License CC-BY 4.0.

PY - 2023

Y1 - 2023

N2 - For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes Ghom(A) and Gsim(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that Ghom(A) = Ghom(B) if and only if A and B are affine equivalent, and Gsim(A) = Gsim(B) if and only if A and B are similar.

AB - For smooth convex disks A, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes Ghom(A) and Gsim(A) of intersection graphs that can be obtained from homothets and similarities of A, respectively. Namely, we prove that Ghom(A) = Ghom(B) if and only if A and B are affine equivalent, and Gsim(A) = Gsim(B) if and only if A and B are similar.

KW - convex disk

KW - geometric intersection graph

KW - homothet

KW - similarity

U2 - 10.4230/LIPIcs.SoCG.2023.2

DO - 10.4230/LIPIcs.SoCG.2023.2

M3 - Article in proceedings

AN - SCOPUS:85163543985

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 16

BT - 39th International Symposium on Computational Geometry, SoCG 2023

A2 - Chambers, Erin W.

A2 - Gudmundsson, Joachim

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 39th International Symposium on Computational Geometry, SoCG 2023

Y2 - 12 June 2023 through 15 June 2023

ER -