The product structure of squaregraphs
Hickingbotham, Robert; Jungeblut, Paul
1; Merker, Laura 1; Wood, David R.
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)
1; Merker, Laura 1; Wood, David R.1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)
Abstract:
A squaregraph is a plane graph in which each internal face is a 4-cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semistrong product of an outerplanar graph and a path. We generalise this result for infinite squaregraphs, and show that this is best possible in the sense that “outerplanar graph” cannot be replaced by “forest”.
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Zeitschriftenaufsatz |
| Publikationsmonat/-jahr | 02.2024 |
| Sprache | Englisch |
| Identifikator | ISSN: 0364-9024, 1097-0118 KITopen-ID: 1000161413 |
| Erschienen in | Journal of Graph Theory |
| Verlag | John Wiley and Sons |
| Band | 105 |
| Heft | 2 |
| Seiten | 179–191 |
| Vorab online veröffentlicht am | 27.07.2023 |
| Schlagwörter | planar graph, product structure, squaregraphs |
| Nachgewiesen in | Dimensions Web of Science Scopus |
| Relationen in KITopen |