## 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 language | English |
---|---|

Title of host publication | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, 16-19 January 2017, FiraBarcelona, Spain |

Place of Publication | New York |

Publisher | Association for Computing Machinery, Inc |

Pages | 2000-2011 |

Number of pages | 12 |

ISBN (Electronic) | 978-161197478-2 |

Publication status | Published - 2017 |

Event | 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) - Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 Conference number: 28 |

### Conference

Conference | 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) |
---|---|

Abbreviated title | SODA 2017 |

Country/Territory | Spain |

City | Barcelona |

Period | 16/01/17 → 19/01/17 |