2024/11/15 by Di Battista, Giuseppe, Grosso, Fabrizio, Maragno, Giulia +1
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2411.10319
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 of practical use to uniformly at random generating the planar embeddings of a graph G or to enumerating such embeddings with amortized constant delay. Also, they can be used to counting, enumerating or uniformly at random generating constrained planar embeddings of G.