Partial and constrained level planarity

G. Brückner, I. Rutter

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

16 Citations (Scopus)

Abstract

Let G = (V;E) be a directed graph and : V ! [k] := f1; : : : ; kg a level assignment such that ℓ(u) <ℓ(v) for all directed edges (u; v) 2 E. A level planar drawing of G is a drawing of G where each vertex v is mapped to a unique point on the horizontal line i with y-coordinate ℓ(v), and each edge is drawn as a y-monotone curve between its endpoints such that no two curves cross in their interior. In the problem Constrained Level Planarity (CLP for short), we are further given a partial ordering ℓi of Vi := 1(i) for i 2 [k], and we seek a level planar drawing where the order 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 ⊆ 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(n5) for CLP of single-source graphs that is based on a simplified version of an existing levelplanarity 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ℓ), where is 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 NPcomplete even when G is a subdivision of a triconnected planar graph with bounded degree.

Original languageEnglish
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, 16-19 January 2017, FiraBarcelona, Spain
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages2000-2011
Number of pages12
ISBN (Electronic)978-161197478-2
Publication statusPublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain
Duration: 16 Jan 201719 Jan 2017
Conference number: 28

Conference

Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)
Abbreviated titleSODA 2017
Country/TerritorySpain
CityBarcelona
Period16/01/1719/01/17

Fingerprint

Dive into the research topics of 'Partial and constrained level planarity'. Together they form a unique fingerprint.

Cite this