In the Partially Embedded Planarity problem, we are given a graph G together with a topological drawing of a subgraph H of G. The task is to decide whether the drawing can be extended to a drawing of the whole graph such that no two edges cross. Angelini et al. gave a linear-time algorithm for solving this problem in 2010 [1, 2]. While their paper constitutes a significant result, the algorithm described therein is highly complex: it uses several layers of decompositions according to connectivity of both G and H, its description spans more than 30 pages, and can hardly be considered implementable. We give an independent linear-time algorithm that works along the well-known vertex-addition planarity test by Booth and Lueker [5, 6]. We modify the PC-tree as underlying data structure used for representing all planar drawing possibilities in a natural way to also respect the restrictions given by the prescribed drawing of the subgraph H. The testing algorithm and its proof of correctness only require small adaptations from the comparatively much simpler generic planarity test, of which several implementations exist. If the test succeeds, an embedding can be constructed using the same approaches that are used for the generic planarity test.

Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. To be more formal, a graph G is a median graph if, for all μ, u, v ∈ V(G), it holds that |I(μ, u) ∩ I(μ, v) ∩ I(u, v)| = 1 where I(x, y) denotes the set of all vertices that lie on shortest paths connecting x and y.

In this paper we are interested in a natural generalization of median graphs, called k-median graphs. A graph G is a k-median graph, if there are k vertices μ₁, …, μ_k ∈ V(G) such that, for all u, v ∈ V(G), it holds that |I(μ_i, u) ∩ I(μ_i, v) ∩ I(u, v)| = 1, 1 ≤ i ≤ k. By definition, every median graph with n vertices is an n-median graph. We provide several characterizations of k-median graphs that, in turn, are used to provide many novel characterizations of median graphs.

The Djoković-Winkler relation Θ is a binary relation defined on the edge set of a given graph that is based on the distances of certain vertices and which plays a prominent role in graph theory. In this paper, we explore the relatively uncharted “reflexive complement” Θ‾ of Θ, where (e,f)∈Θ‾ if and only if e=f or (e,f)∉Θ for edges e and f. We establish the relationship between Θ‾ and the set Δef, comprising the distances between the vertices of e and f and shed some light on the intricacies of its transitive closure ⁎Θ‾⁎. Notably, we demonstrate that ⁎Θ‾⁎ exhibits multiple equivalence classes only within a restricted subclass of complete multipartite graphs. In addition, we characterize non-trivial relations R that coincide with Θ‾ as those where the graph representation is disconnected, with each connected component being the (join of) Cartesian product of complete graphs. The latter results imply, somewhat surprisingly, that knowledge about the distances between vertices is not required to determine ⁎Θ‾⁎. Moreover, ⁎Θ‾⁎ has either exactly one or three equivalence classes.

We combine two fundamental optimization problems related to the construction of phylogenetic trees called maximum rooted triplets consistency and minimally resolved supertree into a new problem, which we call q-maximum rooted triplets consistency (q-MAXRTC). It takes as input a set R of rooted, binary phylogenetic trees with three leaves each and asks for a phylogenetic tree with exactly q internal nodes that contains the largest possible number of trees from R. We prove that q-MAXRTC is NP-hard to approximate within a constant, develop polynomial-time approximation algorithms for different values of q, and show experimentally that representing a phylogenetic tree by one having much fewer nodes typically does not destroy too much branching information. To demonstrate the algorithmic advantage of using trees with few internal nodes, we also propose a new algorithm for computing the rooted triplet distance that is faster than the existing algorithms when restricted to such trees.