Search

We introduce the $k$-Plane Insertion into Plane drawing ($k$-PIP) problem: given a plane drawing of a planar graph $G$ and a set $F$ of edges, insert the edges in $F$ into the drawing such that the resulting drawing is $k$-plane. In this paper, we show that the problem is NP-complete for every $k\ge 1$, even when $G$ is biconnected and the set $F$ of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that $k=1$ and $G$ is a triangulation.

Imagine you are a dog behind a fence $Q$ and a hiker is passing by at constant speed along the hiking path $P$. In order to fulfil your duties as a watchdog, you desire to bark as long as possible at the human. However, your barks can only be heard in a fixed radius $\rho$ and, as a dog, you have bounded speed $s$. Can you optimize your route along the fence $Q$ in order to maximize the barking time with radius $\rho$, assuming you can run backwards and forward at speed at most $s$? We define the barking distance from a polyline $P$ on $n$ vertices to a polyline $Q$ on $m$ vertices as the time that the hiker stays in your barking radius if you run optimally along $Q$. This asymmetric similarity measure between two curves can be used to detect outliers in $Q$ compared to $P$ that other established measures like the Fr\'echet distance and Dynamic Time Warping fail to capture at times. We consider this measure in three different settings. In the discrete setting, the traversals of $P$ and $Q$ are both discrete. For this case we show that the barking distance from $P$ to $Q$ can be computed in $O(nm\log s)$ time. In the semi-discrete setting, the traversal of $Q$ is continuous while the one of $P$ is again discrete. Here, we show how to compute the barking distance in time $O(nm\log (nm))$. Finally, in the continuous setting in which both traversals are continuous, we show that the problem can be solved in polynomial time. For all the settings we show that, assuming SETH, no truly subquadratic algorithm can exist.

We study a variant of the geometric multicut problem, where we are given a set $\mathcal{P}$ of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where $\mathcal{P}$ contains a polygon $Q$ that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an $O(n \log n)$-time algorithm for the case that the convex hull of $\mathcal{P} \setminus \{Q\}$ does not intersect $Q$.

We study the maximum geometric independent set and clique problems in the streaming model. Given a collection of geometric objects arriving in an insertion only stream, the aim is to find a subset such that all objects in the subset are pairwise disjoint or intersect respectively. We show that no constant factor approximation algorithm exists to find a maximum set of independent segments or $2$-intervals without using a linear number of bits. Interestingly, our proof only requires a set of segments whose intersection graph is also an interval graph. This reveals an interesting discrepancy between segments and intervals as there does exist a $2$-approximation for finding an independent set of intervals that uses only $O(\alpha(\mathcal{I})\log |\mathcal{I}|)$ bits of memory for a set of intervals $\mathcal{I}$ with $\alpha(\mathcal{I})$ being the size of the largest independent set of $\mathcal{I}$. On the flipside we show that for the geometric clique problem there is no constant-factor approximation algorithm using less than a linear number of bits even for unit intervals. On the positive side we show that the maximum geometric independent set in a set of axis-aligned unit-height rectangles can be $4$-approximated using only $O(\alpha(\mathcal{R})\log |\mathcal{R}|)$ bits., Comment: 11 pages, 3 figures

Many problems in Discrete and Computational Geometry deal with simple polygons or polygonal regions. Many algorithms and data-structures perform considerably faster, if the underlying polygonal region has low local complexity. One obstacle to make this intuition rigorous, is the lack of a formal definition of local complexity. Here, we give two possible definitions and show how they are related in a combinatorial sense. We say that a polygon $P$ has point visibility width $w=pvw$, if there is no point $q\in P$ that sees more than $w$ reflex vertices. We say that a polygon $P$ has chord visibility width $w=cvw $, if there is no chord $c=\textrm{seg}(a,b)\subset P$ that sees more than w reflex vertices. We show that \[ cvw \leq pvw ^{O( pvw )},\] for any simple polygon. Furthermore, we show that there exists a simple polygon with \[ cvw \geq 2^{\Omega( pvw )}.\], Comment: 7 pages, 5 figures

We introduce a computational origami problem which we call the segment folding problem: given a set of $n$ line-segments in the plane the aim is to make creases along all segments in the minimum number of folding steps. Note that a folding might alter the relative position between the segments, and a segment could split into two. We show that it is NP-hard to determine whether $n$ line segments can be folded in $n$ simple folding operations.

For a class $\mathcal{D}$ of drawings of loopless (multi-)graphs in the plane, a drawing $D \in \mathcal{D}$ is \emph{saturated} when the addition of any edge to $D$ results in $D' \notin \mathcal{D}$ - this is analogous to saturated graphs in a graph class as introduced by Tur\'an (1941) and Erd\H{o}s, Hajnal, and Moon (1964). We focus on $k$-planar drawings, that is, graphs drawn in the plane where each edge is crossed at most $k$ times, and the classes $\mathcal{D}$ of all $k$-planar drawings obeying a number of restrictions, such as having no crossing incident edges, no pair of edges crossing more than once, or no edge crossing itself. While saturated $k$-planar drawings are the focus of several prior works, tight bounds on how sparse these can be are not well understood. We establish a generic framework to determine the minimum number of edges among all $n$-vertex saturated $k$-planar drawings in many natural classes. For example, when incident crossings, multicrossings and selfcrossings are all allowed, the sparsest $n$-vertex saturated $k$-planar drawings have $\frac{2}{k - (k \bmod 2)} (n-1)$ edges for any $k \geq 4$, while if all that is forbidden, the sparsest such drawings have $\frac{2(k+1)}{k(k-1)}(n-1)$ edges for any $k \geq 6$., Comment: Appears in the Proceedings of the 29th International Symposium on Graph Drawing and Network Visualization (GD 2021). This version merges the previous version with some parts of arXiv:2012.02281

In extension problems of partial graph drawings one is given an incomplete drawing of an input graph $G$ and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, only recently it has been shown that the extension problem of simple drawings is NP-hard even when the task is to insert a single edge. In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for $k$-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing.

A drawing of a graph is $k$-plane if no edge is crossed more than $k$ times. In this paper we study saturated $k$-plane drawings with few edges. This are $k$-plane drawings in which no edge can be added without violating $k$-planarity. For every number of vertices $n>k+1$, we present a tight construction with $\frac{n-1}{k+1}$ edges for the case in which the edges can self-intersect. If we restrict the drawings to be $\ell$-simple we show that the number of edges in saturated $k$-plane drawings must be higher. We present constructions with few edges for different values of $k$ and $\ell$. Finally, we investigate saturated straight-line $k$-plane drawings., Comment: This article is partially superseded by and merged with arXiv:2012.08631

The problem of extending partial geometric graph representations such as plane graphs has received considerable attention in recent years. In particular, given a graph $G$, a connected subgraph $H$ of $G$ and a drawing $\mathcal{H}$ of $H$, the extension problem asks whether $\mathcal{H}$ can be extended into a drawing of $G$ while maintaining some desired property of the drawing (e.g., planarity). In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane that allow each edge to have at most one crossing. The most important question identified and left open in that work is whether the problem can be solved in polynomial time when $H$ can be obtained from $G$ by deleting a bounded number of vertices and edges. In this work, we answer this question positively by providing a constructive polynomial-time decision algorithm., Comment: arXiv admin note: text overlap with arXiv:2004.12222

Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph theory and graph drawing. In such an extension problem, we are given a tuple $(G,H,\mathcal{H})$ consisting of a graph $G$, a connected subgraph $H$ of $G$ and a drawing $\mathcal{H}$ of $H$, and the task is to extend $\mathcal{H}$ into a drawing of $G$ while maintaining some desired property of the drawing, such as planarity. In this paper we study the problem of extending partial 1-planar drawings, which are drawings in the plane that allow each edge to have at most one crossing. In addition we consider the subclass of IC-planar drawings, which are 1-planar drawings with independent crossings. Recognizing 1-planar graphs as well as IC-planar graphs is \NP-complete and the \NP-completeness easily carries over to the extension problem. Therefore, our focus lies on establishing the tractability of such extension problems in a weaker sense than polynomial-time tractability. Here, we show that both problems are fixed-parameter tractable when parameterized by the number of edges missing from $H$, i.e., the edge deletion distance between $H$ and $G$. The second part of the paper then turns to a more powerful parameterization which is based on measuring the vertex+edge deletion distance between the partial and complete drawing, i.e., the minimum number of vertices and edges that need to be deleted to obtain $H$ from $G$., Comment: A shortened version of this article has been accepted for presentation and publication at the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)

An embedding of a graph in a book consists of a linear order of its vertices along the spine of the book and of an assignment of its edges to the pages of the book, so that no two edges on the same page cross. The book thickness of a graph is the minimum number of pages over all its book embeddings. Accordingly, the book thickness of a class of graphs is the maximum book thickness over all its members. In this paper, we address a long-standing open problem regarding the exact book thickness of the class of planar graphs, which previously was known to be either three or four. We settle this problem by demonstrating planar graphs that require four pages in any of their book embeddings, thus establishing that the book thickness of the class of planar graphs is four.

We study two new versions of independent and dominating set problems on vertex-colored interval graphs, namely $f$-Balanced Independent Set ($f$-BIS) and $f$-Balanced Dominating Set ($f$-BDS). Let $G=(V,E)$ be a vertex-colored interval graph with a color assignment function $\gamma \colon V \rightarrow \{1,\ldots,k\}$ that maps all vertices in $G$ onto $k$ colors. A subset of vertices $S\subseteq V$ is called $f$-balanced if $S$ contains $f$ vertices from each color class. In the $f$-BIS and $f$-BDS problems, the objective is to compute an independent set or a dominating set that is $f$-balanced. We show that both problems are NP-complete even on proper interval graphs. For the $f$-BIS problem, we design two FPT algorithms, one parameterized by $(f,k)$ for interval graphs and the other parameterized by the vertex cover number for general graphs. Moreover, for an optimization variant of BIS on interval graphs, we show that a simple greedy approach achieves an approximation ratio of $2$., Comment: In Section 4.2 of an earlier version, we presented a local search approach and claimed it was a PTAS for the 1-MCIS problem. After its publication date, we noted that our claim was in contradiction with the APX-hardness result of the Job Interval Scheduling Problem and found a mistake in the proof of our Lemma 9. In this erratum, we removed Section 4.2 and added a correction note

A matching is a set of edges without common endpoint. It was recently shown that every 1-planar graph (i.e., a graph that can be drawn in the plane with at most one crossing per edge) that has minimum degree 3 has a matching of size at least $\frac{n+12}{7}$, and this is tight for some graphs. The proof did not come with an algorithm to find the matching more efficiently than a general-purpose maximum-matching algorithm. In this paper, we give such an algorithm. More generally, we show that any matching that has no augmenting paths of length 9 or less has size at least $\frac{n+12}{7}$ in a 1-planar graph with minimum degree 3.

Label placement in maps is a very challenging task that is critical for the overall map quality. Most previous work focused on designing and implementing fully automatic solutions, but the resulting visual and aesthetic quality has not reached the same level of sophistication that skilled human cartographers achieve. We investigate a different strategy that combines the strengths of humans and algorithms. In our proposed method, first an initial labeling is computed that has many well-placed labels but is not claiming to be perfect. Instead it serves as a starting point for an expert user who can then interactively and locally modify the labeling where necessary. In an iterative human-in-the-loop process alternating between user modifications and local algorithmic updates and refinements the labeling can be tuned to the user's needs. We demonstrate our approach by performing different possible modification steps in a sample workflow with a prototypical interactive labeling editor. Further, we report computational performance results from a simulation experiment in QGIS, which investigates the differences between exact and heuristic algorithms for semi-automatic map labeling. To that end, we compare several alternatives for recomputing the labeling after local modifications and updates, as a major ingredient for an interactive labeling editor., Comment: Extended version of a paper appearing in SIGSPATIAL 2019

A {\em simple drawing} $D(G)$ of a graph $G$ is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge $e$ in the complement of $G$ can be {\em inserted} into $D(G)$ if there exists a simple drawing of $G+e$ extending $D(G)$. As a result of Levi's Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of $G$ can be inserted. In contrast, we show that it is NP -complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles $\mathcal{A}$ and a pseudosegment $\sigma$, it can be decided in polynomial time whether there exists a pseudocircle $\Phi_\sigma$ extending $\sigma$ for which $\mathcal{A}\cup\{\Phi_\sigma\}$ is again an arrangement of pseudocircles., Comment: Full version of the preliminary version published in the proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'20)

A $k$-page linear graph layout of a graph $G = (V,E)$ draws all vertices along a line $\ell$ and each edge in one of $k$ disjoint halfplanes called pages, which are bounded by $\ell$. We consider two types of pages. In a stack page no two edges should cross and in a queue page no edge should be nested by another edge. A crossing (nesting) in a stack (queue) page is called a conflict. The algorithmic problem is twofold and requires to compute (i) a vertex ordering and (ii) a page assignment of the edges such that the resulting layout is either conflict-free or conflict-minimal. While linear layouts with only stack or only queue pages are well-studied, mixed $s$-stack $q$-queue layouts for $s,q \ge 1$ have received less attention. We show NP-completeness results on the recognition problem of certain mixed linear layouts and present a new heuristic for minimizing conflicts. In a computational experiment for the case $s, q = 1$ we show that the new heuristic is an improvement over previous heuristics for linear layouts., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

Partial edge drawing (PED) is a drawing style for non-planar graphs, in which edges are drawn only partially as pairs of opposing stubs on the respective end-vertices. In a PED, by erasing the central parts of edges, all edge crossings and the resulting visual clutter are hidden in the undrawn parts of the edges. In symmetric partial edge drawings (SPEDs), the two stubs of each edge are required to have the same length. It is known that maximizing the ink (or the total stub length) when transforming a straight-line graph drawing with crossings into a SPED is tractable for 2-plane input drawings, but NP-hard for unrestricted inputs. We show that the problem remains NP-hard even for 3-plane input drawings and establish NP-hardness of ink maximization for PEDs of 4-plane graphs. Yet, for k-plane input drawings whose edge intersection graph forms a collection of trees or, more generally, whose intersection graph has bounded treewidth, we present efficient algorithms for computing maximum-ink PEDs and SPEDs. We implemented the treewidth-based algorithms and show a brief experimental evaluation., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

A strict confluent (SC) graph drawing is a drawing of a graph with vertices as points in the plane, where vertex adjacencies are represented not by individual curves but rather by unique smooth paths through a planar system of junctions and arcs. If all vertices of the graph lie in the outer face of the drawing, the drawing is called a strict outerconfluent (SOC) drawing. SC and SOC graphs were first considered by Eppstein et al. in Graph Drawing 2013. Here, we establish several new relationships between the class of SC graphs and other graph classes, in particular string graphs and unit-interval graphs. Further, we extend earlier results about special bipartite graph classes to the notion of strict outerconfluency, show that SOC graphs have cop number two, and establish that tree-like ($\Delta$-)SOC graphs have bounded cliquewidth., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is \NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal $k$-plane set of exteriorly drawn edges for $k \ge 1$, extending the previously studied case $k=0$. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show \NP-hardness for arbitrary $k$, present an efficient algorithm for $k=1$, and generalize it to an explicit \XP-time algorithm for any fixed $k$. For the practically interesting case $k=1$ we implemented our algorithm and present experimental results that confirm the applicability of our algorithm., Comment: This is the full version of a paper with the same title appearing in the proceedings of the 34th International Symposium on Computational Geometry (SoCG) 2018