Abstract We study the recognition complexity of subgraphs of k -connected planar cubic graphs where $${k \in \{0, 1, 2, 3\}}$$ . We present polynomial-time algorithms to recognize subgraphs of 1- and 2-connected planar cubic graphs, both in the variable and fixed embedding setting. The main tools involve the Generalized (Anti)factor -problem for the fixed embedding case, and SPQR-trees for the variable embedding case. Secondly, we prove -hardness of recognizing subgraphs of 3-connected planar cubic graphs in the variable embedding setting.

Abstract We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algebraic sets is bounded by a given threshold is complete for the complexity class $${ \forall \exists _{<}\mathbb {R}} $$ ∀ ∃ < R . This implies that the problem is -, -, $$\exists \mathbb {R} $$ ∃ R -, and $$\forall \mathbb {R} $$ ∀ R -hard.

The stack number of a directed acyclic graph G is the minimum k for which there is a topological ordering of G and a k-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ordering. We prove that the stack number of directed acyclic outerplanar graphs is bounded by a constant, which gives a positive answer to a conjecture by Heath, Pemmaraju and Trenk [SIAM J. Computing, 1999]. As an immediate consequence, this shows that all upward outerplanar graphs have constant stack number, answering a question by Bhore et al. [GD 2021] and thereby making significant progress towards the problem for general upward planar graphs originating from Nowakowski and Parker [Order, 1989]. As our main tool we develop the novel technique of directed H-partitions, which might be of independent interest.We complement the bounded stack number for directed acyclic outerplanar graphs by constructing a family of directed acyclic 2-trees that have unbounded stack number, thereby refuting a conjecture by Nöllenburg and Pupyrev [GD 2023].

Abstract. The page number of a directed acyclic graph [Formula: see text] is the minimum [Formula: see text] for which there is a topological ordering of [Formula: see text] and a [Formula: see text]-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ordering. We address the long-standing open problem asking for the largest page number among all upward planar graphs. We improve the best known lower bound to 5 and present the first asymptotic improvement over the trivial [Formula: see text] upper bound, where [Formula: see text] denotes the number of vertices in [Formula: see text]. Specifically, we first prove that the page number of every upward planar graph is bounded in terms of its width, as well as its height. We then combine both approaches to show that every [Formula: see text]-vertex upward planar graph has page number [Formula: see text].

We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algebraic sets is bounded by a given threshold is complete for the complexity class $\forall\exists_<\mathbb{R}$. This implies that the problem is NP-, co-NP-, $\exists\mathbb{R}$- and $\forall\mathbb{R}$-hard.

It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence 3-edge-colorable. We provide an efficient recognition algorithm that given an $n$-vertex planar graph, augments this graph in $O(n^2)$ steps to a planar cubic bridgeless supergraph, or decides that no such augmentation is possible. The main tools involve the Generalized Antifactor-problem for the fixed embedding case, and SPQR-trees for the variable embedding case.

The page number of a directed acyclic graph G is the minimum k for which there is a topological ordering of G and a k-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ordering. We address the long-standing open problem asking for the largest page number among all upward planar graphs. We improve the best known lower bound to 5 and present the first asymptotic improvement over the trivial (n) upper bound, where n denotes the number of vertices in G. Specifically, we first prove that the page number of every upward planar graph is bounded in terms of its width, as well as its height. We then combine both approaches to show that every n-vertex upward planar graph has page number (n2/3 log2/3(n)).

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.