We propose efficient algorithms for enumerating the celebrated combinatorial structures of maximal planar graphs, called canonical orderings and Schnyder woods, and the related classical graph drawings by de Fraysseix, Pach, and Pollack [Combinatorica, 1990] and by Schnyder [SODA, 1990], called canonical drawings and Schnyder drawings, respectively. To this aim (i) we devise an algorithm for enumerating special e-bipolar orientations of maximal planar graphs, called canonical orientations; (ii) we establish bijections between canonical orientations and canonical drawings, and between canonical orientations and Schnyder drawings; and (iii) we exploit the known correspondence between canonical orientations and canonical orderings, and the known bijection between canonical orientations and Schnyder woods. All our enumeration algorithms have O(n) setup time, space usage, and delay between any two consecutively listed outputs, for an n-vertex maximal planar graph.
Da Lozzo, G., Di Battista, G., Frati, F., Grosso, F., Patrignani, M. (2024). Efficient Enumeration of Drawings and Combinatorial Structures for Maximal Planar Graphs. In WALCOM: Algorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024 (pp.350-364). 152 BEACH ROAD, #21-01/04 GATEWAY EAST, SINGAPORE, 189721, SINGAPORE : SPRINGER-VERLAG SINGAPORE PTE LTD [10.1007/978-981-97-0566-5_25].
Efficient Enumeration of Drawings and Combinatorial Structures for Maximal Planar Graphs
Da Lozzo, Giordano;Di Battista, Giuseppe;Frati, Fabrizio
;Grosso, Fabrizio;Patrignani, Maurizio
2024-01-01
Abstract
We propose efficient algorithms for enumerating the celebrated combinatorial structures of maximal planar graphs, called canonical orderings and Schnyder woods, and the related classical graph drawings by de Fraysseix, Pach, and Pollack [Combinatorica, 1990] and by Schnyder [SODA, 1990], called canonical drawings and Schnyder drawings, respectively. To this aim (i) we devise an algorithm for enumerating special e-bipolar orientations of maximal planar graphs, called canonical orientations; (ii) we establish bijections between canonical orientations and canonical drawings, and between canonical orientations and Schnyder drawings; and (iii) we exploit the known correspondence between canonical orientations and canonical orderings, and the known bijection between canonical orientations and Schnyder woods. All our enumeration algorithms have O(n) setup time, space usage, and delay between any two consecutively listed outputs, for an n-vertex maximal planar graph.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
