Let G be the set of all the planar embeddings of a (not necessarily connected) n-vertex graph G. We present a bijection Φ from G to the natural numbers in the interval [0⋯|G|-1]. Given a planar embedding E of G, we show that Φ(E) can be decomposed into a sequence of O(n) natural numbers each describing a specific feature of E. The function Φ, which is a ranking function for G, can be computed in O(n) time, while its inverse unranking function Φ-1 can be computed in O(nα(n)) time. The results of this paper can be practically applied to uniformly generating the planar embeddings of a graph G at random or to enumerating such embeddings with an amortized constant delay. Additionally, they can be used for counting, enumerating, or uniformly generating constrained planar embeddings of G.
Di Battista, G., Grosso, F., Maragno, G., Patrignani, M. (2025). Ranking and Unranking of the Planar Embeddings of a Planar Graph. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.143-159). Springer Science and Business Media Deutschland GmbH [10.1007/978-981-96-2845-2_10].
Ranking and Unranking of the Planar Embeddings of a Planar Graph
Di Battista G.;Grosso F.;Patrignani M.
2025-01-01
Abstract
Let G be the set of all the planar embeddings of a (not necessarily connected) n-vertex graph G. We present a bijection Φ from G to the natural numbers in the interval [0⋯|G|-1]. Given a planar embedding E of G, we show that Φ(E) can be decomposed into a sequence of O(n) natural numbers each describing a specific feature of E. The function Φ, which is a ranking function for G, can be computed in O(n) time, while its inverse unranking function Φ-1 can be computed in O(nα(n)) time. The results of this paper can be practically applied to uniformly generating the planar embeddings of a graph G at random or to enumerating such embeddings with an amortized constant delay. Additionally, they can be used for counting, enumerating, or uniformly generating constrained planar embeddings of G.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
