Free Sets in Planar Graphs: History and Applications
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916711187349504 |
|---|---|
| author | Dujmović, Vida Morin, Pat |
| author_facet | Dujmović, Vida Morin, Pat |
| contents | A subset $S$ of vertices in a planar graph $G$ is a free set if, for every set $P$ of $|S|$ points in the plane, there exists a straight-line crossing-free drawing of $G$ in which vertices of $S$ are mapped to distinct points in $P$. In this survey, we review - several equivalent definitions of free sets, - results on the existence of large free sets in planar graphs and subclasses of planar graphs, - and applications of free sets in graph drawing. The survey concludes with a list of open problems in this still very active research area. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_17090 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Free Sets in Planar Graphs: History and Applications Dujmović, Vida Morin, Pat Computational Geometry Discrete Mathematics Combinatorics A subset $S$ of vertices in a planar graph $G$ is a free set if, for every set $P$ of $|S|$ points in the plane, there exists a straight-line crossing-free drawing of $G$ in which vertices of $S$ are mapped to distinct points in $P$. In this survey, we review - several equivalent definitions of free sets, - results on the existence of large free sets in planar graphs and subclasses of planar graphs, - and applications of free sets in graph drawing. The survey concludes with a list of open problems in this still very active research area. |
| title | Free Sets in Planar Graphs: History and Applications |
| topic | Computational Geometry Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2403.17090 |