On Comparable Box Dimension
Abstract:
Two boxes in ℝ^d are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in ℝ^d. We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion.
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Proceedingsbeitrag |
| Publikationsjahr | 2022 |
| Sprache | Englisch |
| Identifikator | ISBN: 978-3-9597722-7-3 ISSN: 1868-8969 KITopen-ID: 1000149133 |
| Erschienen in | 38th International Symposium on Computational Geometry (SoCG 2022). Ed.: X. Goaoc |
| Veranstaltung | 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Deutschland, 07.06.2022 – 10.06.2022 |
| Verlag | Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI) |
| Seiten | Art.-Nr.: 38 |
| Serie | Leibniz International Proceedings in Informatics (LIPIcs) ; 224 |
| Schlagwörter | geometric graphs, minor-closed graph classes, treewidth fragility |
| Nachgewiesen in | Scopus |
| Relationen in KITopen |
Seitenaufrufe: 74
seit 29.07.2022
seit 29.07.2022
Downloads: 32
seit 01.08.2022
seit 01.08.2022