2024/03/27 by Olivier Bernardi, Éric Fusy, Bernardi, Olivier +3
Computer Science · Engineering · #3D Modeling in Geospatial Applications #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2403.18980
openalex publication_date 2024/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.