Abstract
The dual of a polyhedron is a polyhedron—or in graph-theoretical terms: the dual of a 3-connected plane graph is a 3-connected plane graph. Astonishingly, except for sufficiently large facewidth, not much is known about the connectivity of the dual on higher surfaces. Are the duals of 3-connected embedded graphs of higher genus 3-connected, too? If not, which connectivity guarantees 3-connectedness of the dual? In this article, we give answers to some of these and related questions. We prove that there is no connectivity that guarantees the 3-connectedness or 2-connectedness of the dual for every genus, and give upper bounds for the minimum genus for which (with (Formula presented.)) a c-connected embedded graph with a dual that has a 1- or 2-cut can occur. We prove that already on the torus, we need 6-connectedness to guarantee 3-connectedness of the dual and 4-connectedness to guarantee 2-connectedness of the dual. In the last section, we answer a related question by Plummer and Zha on orientable embeddings of highly connected noncomplete graphs.
| Original language | English |
|---|---|
| Pages (from-to) | 182-209 |
| Number of pages | 28 |
| Journal | Journal of Graph Theory |
| Volume | 101 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - Oct 2022 |
| Externally published | Yes |
Bibliographical note
Publisher Copyright:© 2022 Wiley Periodicals LLC.
Fingerprint
Dive into the research topics of 'The connectivity of the dual'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver