Source author record

Vincent Kusters

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Computational Complexity Data Structures and Algorithms math.CO

Catalog footprint

Research overview

6works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Arc diagrams, flip distances, and Hamiltonian triangulations

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.

preprint2016arXiv

The Planar Tree Packing Theorem

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 García 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.

preprint2015arXiv

Simultaneous Embeddings with Few Bends and Crossings

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 the common vertices and edges of $R$ and $B$ . 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 (and one bend per edge is sometimes necessary), (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. Our results improve on a paper by Grilli et al. (GD'14), which proves that nine bends per edge suffice, and on a paper by Chan et al. (GD'14), which proves that twenty-four crossings per edge pair suffice.

preprint2015arXiv

The Complexity of Simultaneous Geometric Graph Embedding

Given a collection of planar graphs $G_1,\dots,G_k$ on the same set $V$ of $n$ vertices, the simultaneous geometric embedding (with mapping) problem, or simply $k$ -SGE, is to find a set $P$ of $n$ points in the plane and a bijection $ϕ: V \to P$ such that the induced straight-line drawings of $G_1,\dots,G_k$ under $ϕ$ are all plane. This problem is polynomial-time equivalent to weak rectilinear realizability of abstract topological graphs, which Kynčl (doi:10.1007/s00454-010-9320-x) proved to be complete for $\exists\mathbb{R}$ , the existential theory of the reals. Hence the problem $k$ -SGE is polynomial-time equivalent to several other problems in computational geometry, such as recognizing intersection graphs of line segments or finding the rectilinear crossing number of a graph. We give an elementary reduction from the pseudoline stretchability problem to $k$ -SGE, with the property that both numbers $k$ and $n$ are linear in the number of pseudolines. This implies not only the $\exists\mathbb{R}$ -hardness result, but also a $2^{2^{Ω(n)}}$ lower bound on the minimum size of a grid on which any such simultaneous embedding can be drawn. This bound is tight. Hence there exists such collections of graphs that can be simultaneously embedded, but every simultaneous drawing requires an exponential number of bits per coordinates. The best value that can be extracted from Kynčl's proof is only $2^{2^{Ω(\sqrt{n})}}$ .

preprint2014arXiv

Halving Balls in Deterministic Linear Time

Let $\D$ be a set of $n$ pairwise disjoint unit balls in $\R^d$ and $P$ the set of their center points. A hyperplane $\Hy$ is an \emph{ $m$ -separator} for $\D$ if each closed halfspace bounded by $\Hy$ contains at least $m$ points from $P$ . This generalizes the notion of halving hyperplanes, which correspond to $n/2$ -separators. The analogous notion for point sets has been well studied. Separators have various applications, for instance, in divide-and-conquer schemes. In such a scheme any ball that is intersected by the separating hyperplane may still interact with both sides of the partition. Therefore it is desirable that the separating hyperplane intersects a small number of balls only. We present three deterministic algorithms to bisect or approximately bisect a given set of disjoint unit balls by a hyperplane: Firstly, we present a simple linear-time algorithm to construct an $αn$ -separator for balls in $\R^d$ , for any $0<α<1/2$ , that intersects at most $cn^{(d-1)/d}$ balls, for some constant $c$ that depends on $d$ and $α$ . The number of intersected balls is best possible up to the constant $c$ . Secondly, we present a near-linear time algorithm to construct an $(n/2-o(n))$ -separator in $\R^d$ that intersects $o(n)$ balls. Finally, we give a linear-time algorithm to construct a halving line in $\R^2$ that intersects $O(n^{(5/6)+ε})$ disks. Our results improve the runtime of a disk sliding algorithm by Bereg, Dumitrescu and Pach. In addition, our results improve and derandomize an algorithm to construct a space decomposition used by L{ö}ffler and Mulzer to construct an onion (convex layer) decomposition for imprecise points (any point resides at an unknown location within a given disk).

preprint2013arXiv

On Universal Point Sets for Planar Graphs

A set P of points in R^2 is n-universal, if every planar graph on n vertices admits a plane straight-line embedding on P. Answering a question by Kobourov, we show that there is no n-universal point set of size n, for any n>=15. Conversely, we use a computer program to show that there exist universal point sets for all n<=10 and to enumerate all corresponding order types. Finally, we describe a collection G of 7'393 planar graphs on 35 vertices that do not admit a simultaneous geometric embedding without mapping, that is, no set of 35 points in the plane supports a plane straight-line embedding of all graphs in G.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.