In the longest plane spanning tree problem, we are given a finite planar point set \(\mathcal{P}\) , and our task is to find a plane (i.e., noncrossing) spanning tree for \(\mathcal{P}\) with maximum total Euclidean edge length. Despite more than two decades of research, it remains open whether this problem is NP-hard. Thus, previous results have focused on polynomial-time algorithms that produce plane trees whose total edge length approximates \(\mathrm{OPT}\) , the maximum possible length. The approximate trees in these algorithms all have small unweighted diameter, typically two to four. It is natural to ask whether this is a common feature of longest plane spanning trees, or an artifact of the specific approximation algorithms. We provide three results to elucidate the interplay between the approximation guarantee and the unweighted diameter of the approximate trees. First, we describe a polynomial-time algorithm to construct a plane tree with diameter at most four and total edge length at least \(0.546\cdot\mathrm{OPT}\) . This constitutes a substantial improvement over the state of the art. Second, we show that a longest plane tree among those with diameter at most three can be found in polynomial time. Third, for any candidate diameter \(d\geq 3\) , we provide upper bounds on the approximation factor that can be achieved by a longest plane tree with diameter at most \( d \) (compared to a longest plane tree without constraints).

We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three crossings. We show how the recently developed Density Formula for topological drawings of graphs [Kaufmann et al., 2024] can be used to count the crossings in terms of the number n of vertices. As a main result, we show that every 3-plane drawing has at most 5.5(n-2) crossings, which is tight. In particular, it follows that every 3-planar graph on n vertices has crossing number at most 5.5n, which improves upon a recent bound [Bekos et al., 2024] of 6.6n. To apply the Density Formula, we carefully analyze the interplay between certain configurations of cells in a 3-plane drawing. As a by-product, we also obtain an alternative proof for the known statement that every 3-planar graph has at most 5.5(n-2) edges.

Merge trees are a powerful tool from topological data analysis that is frequently used to analyze scalar fields. The similarity between two merge trees can be captured by an interleaving: a pair of maps between the trees that jointly preserve ancestor relations in the trees. Interleavings can have a complex structure; visualizing them requires a sense of (drawing) order which is not inherent in this purely topological concept. However, in practice it is often desirable to introduce additional geometric constraints, which leads to variants such as labeled or monotone interleavings. Monotone interleavings respect a given order on the leaves of the merge trees and hence have the potential to be visualized in a clear and comprehensive manner.In this paper, we introduce ParkView: a schematic, scalable encoding for monotone interleavings. ParkView captures both maps of the interleaving using an optimal decomposition of both trees into paths and corresponding branches. We prove several structural properties of monotone interleavings, which support a sparse visual encoding using active paths and hedges that can be linked using a maximum of 6 colors for merge trees of arbitrary size. We show how to compute an optimal path-branch decomposition in linear time and illustrate ParkView on a number of real-world datasets.

Abstract. An obstacle representation of a graph [Formula: see text] consists of a set of pairwise disjoint simply connected closed regions and a one-to-one mapping of the vertices of [Formula: see text] to points such that two vertices are adjacent in [Formula: see text] if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each [Formula: see text]-vertex graph is [Formula: see text] [M. Balko, J. Cibulka, and P. Valtr, Discrete Comput. Geom., 59 (2018), pp. 143–164] and that there are [Formula: see text]-vertex graphs whose obstacle number is [Formula: see text] [V. Dujmović and P. Morin, Electron. J. Combin., 22 (2015), 3.1]. We improve this lower bound to [Formula: see text] for simple polygons and to [Formula: see text] for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of [Formula: see text]-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some [Formula: see text]-vertex graph is given as part of the input, then for some drawings [Formula: see text] obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph [Formula: see text] is fixed-parameter tractable in the vertex cover number of [Formula: see text]. Second, we show that, given a graph [Formula: see text] and a simple polygon [Formula: see text], it is NP-hard to decide whether [Formula: see text] admits an obstacle representation using [Formula: see text] as the only obstacle.

A \emph{book-embedding} of a graph $G$ is an embedding of vertices of $G$ along the spine of a book, and edges of $G$ on the pages so that no two edges on the same page intersect. the minimum number of pages in which a graph can be embedded is called the \emph{page number}. The book-embedding of graphs may be important in several technical applications, e.g., sorting with parallel stacks, fault-tolerant processor arrays design, and layout problems with application to very large scale integration (VLSI). Bernhart and Kainen firstly considered the book-embedding of the planar graph and conjectured that its page number can be made arbitrarily large [JCT, 1979, 320-331]. Heath [FOCS84] found that planar graphs admit a seven-page book embedding. Later, Yannakakis proved that four pages are necessary and sufficient for planar graphs in [STOC86]. Recently, Bekos et al. [STACS14] described an $O(n^{2})$ time algorithm of two-page book embedding for 4-planar graphs. In this paper, we embed 5-planar graphs into a book of three pages by an $O(n^{2})$ time algorithm.

It is shown that every 2-planar graph is quasiplanar, that is, if a simple graph admits a drawing in the plane such that every edge is crossed at most twice, then it also admits a drawing in which no three edges pairwise cross. We further show that quasiplanarity is witnessed by a simple topological drawing, that is, any two edges cross at most once and adjacent edges do not cross.

Packing graphs is a combinatorial problem where several given graphs are being mapped into a common host graph such that every edge is used at most once. In the planar tree packing problem we are given two trees T1 and T2 on n vertices and have to find a planar graph on n vertices that is the edge-disjoint union of T1 and T2. A clear exception that must be made is the star which cannot be packed together with any other tree. But according to a conjecture of Garcia et al. from 1997 this is the only exception, and all other pairs of trees admit a planar packing. Previous results addressed various special cases, such as a tree and a spider tree, a tree and a caterpillar, two trees of diameter four, two isomorphic trees, and trees of maximum degree three. Here we settle the conjecture in the affirmative and prove its general form, thus making it the planar tree packing theorem. The proof is constructive and provides a polynomial time algorithm to obtain a packing for two given nonstar trees.

A simultaneous embedding with fixed edges ( Sefe ) of two planar graphs R and B is a pair of plane drawings of R and B that coincide when restricted to their common vertices and edges. We show that whenever R and B admit a Sefe , they also admit a Sefe in which every edge is a polygonal curve with few bends and every pair of edges has few crossings. Specifically: (1) if R and B are trees then one bend per edge and four crossings per edge pair suffice, (2) if R is a planar graph and B is a tree then six bends per edge and eight crossings per edge pair suffice, and (3) if R and B are planar graphs then six bends per edge and sixteen crossings per edge pair suffice. This improves on results by Grilli et al. (GD’14), who prove that nine bends per edge suffice, and by Chan et al. (GD’14), who prove that twenty-four crossings per edge pair suffice. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We show that every triangulation (maximal planar graph) on n\ge 6 vertices can be flipped into a Hamiltonian triangulation using a sequence of less than n/2 combinatorial edge flips. The previously best upper bound uses 4-connectivity as a means to establish Hamiltonicity. But in general about 3n/5 flips are necessary to reach a 4-connected triangulation. Our result improves the upper bound on the diameter of the flip graph of combinatorial triangulations on n vertices from 5.2n-33.6 to 5n-23. We also show that for every triangulation on n vertices there is a simultaneous flip of less than 2n/3 edges to a 4-connected triangulation. The bound on the number of edges is tight, up to an additive constant. As another application we show that every planar graph on n vertices admits an arc diagram with less than n/2 biarcs, that is, after subdividing less than n/2 (of potentially 3n-6) edges the resulting graph admits a 2-page book embedding.

We show that it is an NP-hard problem to decide for a given set P of n points in the Euclidean plane and a given parameter k∈R, whether P admits a spanning tree of maximum vertex degree four whose sum of edge lengths does not exceed k.

For n disjoint line segments in the plane we construct in optimal O(n log n) time an en-compassing tree of maximum degree three such that at every vertex all incident edges lie in a halfplane defined by the incident input segment. In particular, this implies that each vertex is pointed. Furthermore, we show that any set of colored disjoint line segments (for each segment one endpoint is colored red and the other endpoint is colored blue) has an encompassing tree of maximum degree three in which no edge is monochromatic.