A census of graph-drawing algorithms based on generalized transversal structures
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913713745821696 |
|---|---|
| author | Bernardi, Olivier Fusy, Éric Liang, Shizhe |
| author_facet | Bernardi, Olivier Fusy, Éric Liang, Shizhe |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18980 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A census of graph-drawing algorithms based on generalized transversal structures Bernardi, Olivier Fusy, Éric Liang, Shizhe Combinatorics Computational Geometry 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. |
| title | A census of graph-drawing algorithms based on generalized transversal structures |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2403.18980 |