Grounded String Representations of Series-Parallel Graphs without Transitive Edges
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914365126475776 |
|---|---|
| author | Cornelsen, Sabine Kratochvíl, Jan Münch, Miriam Ortali, Giacomo Weinberger, Alexandra Wolff, Alexander |
| author_facet | Cornelsen, Sabine Kratochvíl, Jan Münch, Miriam Ortali, Giacomo Weinberger, Alexandra Wolff, Alexander |
| contents | In a {\em grounded string representation} of a graph there is a horizontal line $\ell$ and each vertex is represented as a simple curve below $\ell$ with one end point on $\ell$ such that two curves intersect if and only if the respective vertices are adjacent. A grounded string representation is a {\em grounded L-reverseL-representation} if each vertex is represented by a 1-bend orthogonal polyline. It is a {\em grounded L-representation} if in addition all curves are L-shaped. We show that every biconnected series-parallel graph without edges between the two vertices of a separation pair (i.e., {\em transitive edges}) admits a grounded L-reverseL-representation if and only if it admits a grounded string representation. Moreover, we can test in linear time whether such a representation exists. We also construct a biconnected series-parallel graph without transitive edges that admits a grounded L-reverseL-representation, but no grounded L-representation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_02827 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Grounded String Representations of Series-Parallel Graphs without Transitive Edges Cornelsen, Sabine Kratochvíl, Jan Münch, Miriam Ortali, Giacomo Weinberger, Alexandra Wolff, Alexander Computational Geometry In a {\em grounded string representation} of a graph there is a horizontal line $\ell$ and each vertex is represented as a simple curve below $\ell$ with one end point on $\ell$ such that two curves intersect if and only if the respective vertices are adjacent. A grounded string representation is a {\em grounded L-reverseL-representation} if each vertex is represented by a 1-bend orthogonal polyline. It is a {\em grounded L-representation} if in addition all curves are L-shaped. We show that every biconnected series-parallel graph without edges between the two vertices of a separation pair (i.e., {\em transitive edges}) admits a grounded L-reverseL-representation if and only if it admits a grounded string representation. Moreover, we can test in linear time whether such a representation exists. We also construct a biconnected series-parallel graph without transitive edges that admits a grounded L-reverseL-representation, but no grounded L-representation. |
| title | Grounded String Representations of Series-Parallel Graphs without Transitive Edges |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.02827 |