Current browse context:
math.CO
Change to browse by:
References & Citations
Mathematics > Combinatorics
Title: A census of graph-drawing algorithms based on generalized transversal structures
(Submitted on 27 Mar 2024)
Abstract: We define graph drawing algorithms which simultaneously generalize several classical ones. More precisely, we consider the following algorithms:
(a) Fusy's algorithm for the straight-line grid drawing of planar triangulations, based on transversal structures,
(b) Barri\`ere and Huemmer's algorithm for the straight-line grid drawing of planar quadrangulations, based on separating decompositions,
(c) He's algorithm for the orthogonal drawing of 3-valent planar maps, based on transversal structures,
(d) Bernardi \& Fusy 's algorithm for the orthogonal drawing of 4-valent planar maps, based on 2-orientations.
We present an algorithm generalizing (a) and (b) which produces a straight line grid drawing for planar maps with faces of degree at most 4, and we present an algorithm generalizing (c) and (d) which produces an orthogonal drawing for planar maps with vertices of degree at most 4. Our two algorithms are based on a class of combinatorial structures called grand-Schnyder woods.
Submission history
From: Olivier Bernardi [view email][v1] Wed, 27 Mar 2024 19:55:50 GMT (2790kb,D)
Link back to: arXiv, form interface, contact.