Skip to main navigation Skip to search Skip to main content

The connectivity of the dual

  • University of Maribor
  • Ghent University
  • Babes-Bolyai University

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 languageEnglish
Pages (from-to)182-209
Number of pages28
JournalJournal of Graph Theory
Volume101
Issue number2
DOIs
Publication statusPublished - Oct 2022
Externally publishedYes

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