Hypergraphs as Metro Maps: Drawing Paths with Few Bends in Trees, Cacti, and Plane 4-Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914173446782976 |
|---|---|
| author | Cornelsen, Sabine Förster, Henry Gupta, Siddharth Kobourov, Stephen Zink, Johannes |
| author_facet | Cornelsen, Sabine Förster, Henry Gupta, Siddharth Kobourov, Stephen Zink, Johannes |
| contents | A hypergraph consists of a set of vertices and a set of subsets of vertices, called hyperedges. In the metro map metaphor, each hyperedge is represented by a path (the metro line) and the union of all these paths is the support graph (metro network) of the hypergraph. Formally speaking, a path-based support is a graph together with a set of paths. We consider the problem of constructing drawings of path-based supports that (i) minimize the sum of the number of bends on all paths, (ii) minimize the maximum number of bends on any path, or (iii) maximize the number of 0-bend paths, then the number of 1-bend paths, etc. We concentrate on straight-line drawings of path-based tree and cactus supports as well as orthogonal drawings of path-based plane supports with maximum degree 4. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22508 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hypergraphs as Metro Maps: Drawing Paths with Few Bends in Trees, Cacti, and Plane 4-Graphs Cornelsen, Sabine Förster, Henry Gupta, Siddharth Kobourov, Stephen Zink, Johannes Computational Geometry A hypergraph consists of a set of vertices and a set of subsets of vertices, called hyperedges. In the metro map metaphor, each hyperedge is represented by a path (the metro line) and the union of all these paths is the support graph (metro network) of the hypergraph. Formally speaking, a path-based support is a graph together with a set of paths. We consider the problem of constructing drawings of path-based supports that (i) minimize the sum of the number of bends on all paths, (ii) minimize the maximum number of bends on any path, or (iii) maximize the number of 0-bend paths, then the number of 1-bend paths, etc. We concentrate on straight-line drawings of path-based tree and cactus supports as well as orthogonal drawings of path-based plane supports with maximum degree 4. |
| title | Hypergraphs as Metro Maps: Drawing Paths with Few Bends in Trees, Cacti, and Plane 4-Graphs |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2511.22508 |