Weakly leveled planarity with bounded span

doi:10.1016/j.tcs.2026.115811

Weakly leveled planarity with bounded span

2026-02-01

0

PRE

AI

DOI：10.1016/j.tcs.2026.115811

Original

Original request for help

Save

Abstract

En 中文

This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly y-monotone curve. A graph is s-span weakly leveled planar if it admits such a drawing where the edges have span at most s; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing s-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NPhard with respect to its natural parameter s and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of 2-outerplanar graphs generalizing Halin graphs, are Theta(log n)-span weakly leveled planar and 4-span weakly leveled planar when 3-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.

Keywords:

Leveled planar graphs

Edge span

Graph drawing

Edge-length ratio

Weakly leveled planarity with bounded span

Abstract

Journal

Organization