Segment Intersection Representations, Level Planarity and Constrained Ordering Problems

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F26%3A10515269" target="_blank" >RIV/00216208:11320/26:10515269 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/978-3-032-11835-6_15" target="_blank" >https://doi.org/10.1007/978-3-032-11835-6_15</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-032-11835-6_15" target="_blank" >10.1007/978-3-032-11835-6_15</a>

Result language

angličtina

Original language name

Segment Intersection Representations, Level Planarity and Constrained Ordering Problems

Original language description

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 THERE EXISTS R-complete [21]) in the general case [15] and remains so if we restrict the segments to be axis-aligned, i.e., horizontal and vertical [14]. 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 [14, 16]. We resolve this question by giving efficient quartic-time 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 if all edges connect adjacent levels. 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX23-04949X" target="_blank" >GX23-04949X: Fundamental questions of discrete geometry</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2026

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Lecture Notes in Computer Science

ISBN

978-3-032-11834-9

ISSN

—

e-ISSN

1611-3349

Number of pages

14

Pages from-to

205-218

Publisher name

Springer Nature

Place of publication

Cham

Event location

Graph-Theoretic Concepts in Computer Science

Event date

Jun 11, 2025

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—