Bibliographic Details
| Title: |
Partial and constrained level planarity. |
| Authors: |
Brückner, Guido1 (AUTHOR) brueckner@kit.edu, Rutter, Ignaz1,2 (AUTHOR) rutter@fim.uni-passau.de |
| Source: |
Theoretical Computer Science. Aug2025, Vol. 1045, pN.PAG-N.PAG. 1p. |
| Subjects: |
Polynomial time algorithms, Data structures, Linear orderings, Graph algorithms, Planar graphs, Directed graphs |
| Abstract: |
Let G = (V , E) be a directed graph and ℓ : V → [ k ] : = { 1 , 2 , ... , k } a level assignment such that ℓ (u) < ℓ (v) for all directed edges (u , v) ∈ E. A level-planar drawing of G maps each vertex v to a unique point on the horizontal line ℓ with y -coordinate ℓ (v) and each directed edge to a y -monotone Jordan arc between its endpoints such that no two arcs cross in their interior. In the problem Constrained Level Planarity (CLP for short), we are further given a partial ordering ◁ i of V i : = ℓ − 1 (i) for each i ∈ [ k ] , and we seek a level-planar drawing where the linear order ≺ i of the vertices on ℓ i is a linear extension of ◁ i. A special case of this is the problem Partial Level Planarity (PLP for short), where we are asked to extend a given level-planar drawing H of a subgraph H of G to a complete drawing G of G without modifying the given drawing, i.e., the restriction of G to H must coincide with H. We give a simple polynomial-time algorithm with running time O (n 5) for CLP of single-source graphs that is based on a simplified version of an existing level-planarity testing algorithm for single-source graphs. We introduce a modified type of PQ-tree data structure that is capable of efficiently handling the arising constraints to improve the running time to O (n + k s) , where s denotes the size of the constraints. We complement this result by showing that PLP is NP -complete even in very restricted cases. In particular, PLP remains NP -complete even when G has a constant number of levels, and when G is a subdivision of a triconnected planar graph with bounded degree. [ABSTRACT FROM AUTHOR] |
|
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
