Structural similarity between polyhedral embeddings and their duals and its application to self-duality of pathwidth
Let $G$ be a graph embedded on a closed surface. We call $G$ a \emph{polyhedral embedding} if all facial walks are cycles, and any two of them are either disjoint or intersect in a single vertex or a single edge. In this paper, we present a new bound on the relation between the pathwidth of a polyhedral embedding and its dual. More precisely, we prove that for a polyhedral embedding $G$ on a closed surface with Euler characteristic $χ$, $\mathsf{pw}(G^*) \leq 3\ \mathsf{pw}(G)+c$, where $c$ is a constant depending only on $χ$. This result improves the coefficient of $\mathsf{pw}(G)$ in the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.19095
curl -X POST /api/v1/records/arxiv/2602.19095/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.19095/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'