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 The partial representation extension problem generalizes the recognition problem for geometric intersection graphs. The input consists of a graph G, a subgraph $$H \subseteq G$$ H ⊆ G and a representation $$\mathcal R'$$ R ′ of H. The question is whether G admits a representation $$\mathcal R$$ R whose restriction to H is $$\mathcal R'$$ R ′ . We study this question for circle graphs, which are intersection graphs of chords of a circle. Their representations are called chord diagrams. We show that for a graph with n vertices and m edges the partial representation extension problem can be solved in $$O((n + m) \alpha (n + m))$$ O ( ( n + m ) α ( n + m ) ) time, thereby improving over an $$O(n^3)$$ O ( n 3 ) -time algorithm by Chaplick et al. (J Graph Theory 91(4), 365–394, 2019). The main technical contributions are a canonical way of orienting chord diagrams and a novel compact representation of the set of all canonically oriented chord diagrams that represent a given circle graph G, which is of independent interest.

Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time $O((n+m)α(n+m))$ where $n$ is the number of vertices, $m$ is the number of edges and $α$ is the inverse Ackermann function. Our algorithm is based on the minimal split decomposition [Cunnigham, 1982] and uses the state-of-art circle graph recognition algorithm [Gioan, Paul, Tedder, Corneil, 2014] in the same running time. It improves the running time $O(nm)$ of the previous algorithm [Hsu, 1995] based on a similar approach.

An SPQR-tree is a data structure that efficiently represents all planar embeddings of a biconnected planar graph. It is a key tool in a number of constrained planarity testing algorithms, which seek a planar embedding of a graph subject to some given set of constraints. We develop an SPQR-tree-like data structure that represents all level-planar embeddings of a biconnected level graph with a single source, called the LP-tree, and give a simple algorithm to compute it in linear time. Moreover, we show that LP-trees can be used to adapt three constrained planarity algorithms to the level-planar case by using them as a drop-in replacement for SPQR-trees.

Abstract We introduce and study level-planar straight-line drawings with a fixed number $$\lambda $$ λ of slopes. For proper level graphs (all edges connect vertices of adjacent levels), we give an $$O(n \log ^2 n / \log \log n)$$ O ( n log 2 n / log log n ) -time algorithm that either finds such a drawing or determines that no such drawing exists. Moreover, we consider the partial drawing extension problem, where we seek to extend an immutable drawing of a subgraph to a drawing of the whole graph, and the simultaneous drawing problem, which asks about the existence of drawings of two graphs whose restrictions to their shared subgraph coincide. We present $$O(n^{4/3} \log n)$$ O ( n 4 / 3 log n ) -time and $$O(\lambda n^{10/3} \log n)$$ O ( λ n 10 / 3 log n ) -time algorithms for these respective problems on proper level-planar graphs. We complement these positive results by showing that testing whether non-proper level graphs admit level-planar drawings with $$\lambda $$ λ slopes is -hard even in restricted cases.

In this paper, we introduce and study multilevel planarity, a generalization of upward planarity and level planarity. Let $G = (V, E)$ be a directed graph and let $\ell: V \to \mathcal P(\mathbb Z)$ be a function that assigns a finite set of integers to each vertex. A multilevel-planar drawing of $G$ is a planar drawing of $G$ such that for each vertex $v\in V$ its $y$-coordinate $y(v)$ is in $\ell(v)$, and each edge is drawn as a strictly $y$-monotone curve. We present linear-time algorithms for testing multilevel planarity of embedded graphs with a single source and of oriented cycles. Complementing these algorithmic results, we show that multilevel-planarity testing is $\textsf{NP}$-complete even in very restricted cases.

Let G = (V, E) be a directed graph and ℓ: V → [k] := {1,…, k} a level assignment such that ℓ(u) < ℓ(v) for all directed edges (u, v) ∊ 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 íj 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 of Vi := ℓ−1(i) for i ∊ [k], and we seek a level planar drawing where the order of the vertices on ℓi is a linear extension of 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 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ℓ), 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 NP- complete even when G is a subdivision of a triconnected planar graph with bounded degree.