A census of graph-drawing algorithms based on generalized transversal structures
<|reference_start|>A census of graph-drawing algorithms based on generalized transversal structures: We present two graph drawing algorithms based on the recently defined "grand-Schnyder woods", which are a far-reaching generalization of the classical Schnyder woods. The first is a straight-line drawing algorithm for plane graphs with faces of degree 3 and 4 with no separating 3-cycle, while the second is a rectangular drawing algorithm for the dual of such plane graphs.   In our algorithms, the coordinates of the vertices are defined in a global manner, based on the underlying grand-Schnyder woods. The grand-Schnyder woods and drawings are computed in linear time.   When specializing our algorithms to special classes of plane graphs, we recover the following known algorithms: (1) He's algorithm for rectangular drawing of 3-valent plane graphs, based on transversal structures, (2) Fusy's algorithm for the straight-line drawing of triangulations of the square, based on transversal structures, (3) Bernardi and Fusy's algorithm for the orthogonal drawing of 4-valent plane graphs, based on 2-orientations, (4) Barriere and Huemer's algorithm for the straight-line drawing of quadrangulations, based on separating decompositions.   Our contributions therefore provide a unifying perspective on a large family of graph drawing algorithms that were originally defined on different classes of plane graphs and were based on seemingly different combinatorial structures.<|reference_end|>
@article{bernardi2024a,
    title={A census of graph-drawing algorithms based on generalized transversal
  structures},
    author={Olivier Bernardi, 'Eric Fusy, Shizhe Liang},
    journal={arXiv preprint arXiv:2403.18980},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.18980},
    primaryClass={math.CO cs.CG}
}