Segment Intersection Representations, Level Planarity and Constrained Ordering Problems
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_ | 1866929727182209024 |
|---|---|
| author | Fink, Simon D. Pfretzschner, Matthias Stumpf, Peter |
| author_facet | Fink, Simon D. Pfretzschner, Matthias Stumpf, Peter |
| contents | In the Segment Intersection Graph Representation Problem, we want to represent the vertices of a graph as straight line segments in the plane such that two segments cross if and only if there is an edge between the corresponding vertices. This problem is NP-hard (even $\exists\mathbb{R}$-complete [Schaefer, 2010]) in the general case [Kratochvíl & Neŝetril, 1992] and remains so if we restrict the segments to be axis-aligned, i.e., horizontal and vertical [Kratochvíl, 1994]. A long standing open question for the latter variant is its complexity when the order of segments along one axis (say the vertical order of horizontal segments) is already given [Kratochvíl & Neŝetril, 1992; Kratochvíl, 1994].
We resolve this question by giving efficient solutions using two very different approaches that are interesting on their own. First, using a graph-drawing perspective, we relate the problem to a variant of the well-known Level Planarity problem, where vertices have to lie on pre-assigned horizontal levels. In our case, each level also carries consecutivity constraints on its vertices; this Level Planarity variant is known to have a quadratic solution.
Second, we use an entirely combinatorial approach, and show that both problems can equivalently be formulated as a linear ordering problem subject to certain consecutivity constraints. While the complexity of such problems varies greatly, we show that in this case the constraints are well-structured in a way that allows a direct quadratic solution. Thus, we obtain three different-but-equivalent perspectives on this problem: the initial geometric one, one from planar graph drawing and a purely combinatorial one. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16621 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Segment Intersection Representations, Level Planarity and Constrained Ordering Problems Fink, Simon D. Pfretzschner, Matthias Stumpf, Peter Computational Geometry In the Segment Intersection Graph Representation Problem, we want to represent the vertices of a graph as straight line segments in the plane such that two segments cross if and only if there is an edge between the corresponding vertices. This problem is NP-hard (even $\exists\mathbb{R}$-complete [Schaefer, 2010]) in the general case [Kratochvíl & Neŝetril, 1992] and remains so if we restrict the segments to be axis-aligned, i.e., horizontal and vertical [Kratochvíl, 1994]. A long standing open question for the latter variant is its complexity when the order of segments along one axis (say the vertical order of horizontal segments) is already given [Kratochvíl & Neŝetril, 1992; Kratochvíl, 1994]. We resolve this question by giving efficient solutions using two very different approaches that are interesting on their own. First, using a graph-drawing perspective, we relate the problem to a variant of the well-known Level Planarity problem, where vertices have to lie on pre-assigned horizontal levels. In our case, each level also carries consecutivity constraints on its vertices; this Level Planarity variant is known to have a quadratic solution. Second, we use an entirely combinatorial approach, and show that both problems can equivalently be formulated as a linear ordering problem subject to certain consecutivity constraints. While the complexity of such problems varies greatly, we show that in this case the constraints are well-structured in a way that allows a direct quadratic solution. Thus, we obtain three different-but-equivalent perspectives on this problem: the initial geometric one, one from planar graph drawing and a purely combinatorial one. |
| title | Segment Intersection Representations, Level Planarity and Constrained Ordering Problems |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2502.16621 |