Partial and constrained level planarity.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 185304719 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Partial and constrained level planarity. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Brückner%2C+Guido%22">Brückner, Guido</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> brueckner@kit.edu</i><br /><searchLink fieldCode="AR" term="%22Rutter%2C+Ignaz%22">Rutter, Ignaz</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> rutter@fim.uni-passau.de</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theoretical+Computer+Science%22">Theoretical Computer Science</searchLink>. Aug2025, Vol. 1045, pN.PAG-N.PAG. 1p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Polynomial+time+algorithms%22">Polynomial time algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Data+structures%22">Data structures</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+orderings%22">Linear orderings</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+algorithms%22">Graph algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Planar+graphs%22">Planar graphs</searchLink><br /><searchLink fieldCode="DE" term="%22Directed+graphs%22">Directed graphs</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=185304719 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.tcs.2025.115291 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 1 StartPage: N.PAG Subjects: – SubjectFull: Polynomial time algorithms Type: general – SubjectFull: Data structures Type: general – SubjectFull: Linear orderings Type: general – SubjectFull: Graph algorithms Type: general – SubjectFull: Planar graphs Type: general – SubjectFull: Directed graphs Type: general Titles: – TitleFull: Partial and constrained level planarity. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Brückner, Guido – PersonEntity: Name: NameFull: Rutter, Ignaz IsPartOfRelationships: – BibEntity: Dates: – D: 11 M: 08 Text: Aug2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 03043975 Numbering: – Type: volume Value: 1045 Titles: – TitleFull: Theoretical Computer Science Type: main |
| ResultId | 1 |
