Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.02827 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |