BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Oswin Aichholzer

Oswin Aichholzer contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational Geometrymath.COData Structures and AlgorithmsDiscrete MathematicsComputational Complexity

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
14works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

14 published item(s)

preprint2022arXiv

Compatible Spanning Trees in Simple Drawings of $K_n$

For a simple drawing $D$ of the complete graph $K_n$, two (plane) subdrawings are compatible if their union is plane. Let $\mathcal{T}_D$ be the set of all plane spanning trees on $D$ and $\mathcal{F}(\mathcal{T}_D)$ be the compatibility graph that has a vertex for each element in $\mathcal{T}_D$ and two vertices are adjacent if and only if the corresponding trees are compatible. We show, on the one hand, that $\mathcal{F}(\mathcal{T}_D)$ is connected if $D$ is a cylindrical, monotone, or strongly c-monotone drawing. On the other hand, we show that the subgraph of $\mathcal{F}(\mathcal{T}_D)$ induced by stars, double stars, and twin stars is also connected. In all cases the diameter of the corresponding compatibility graph is at most linear in $n$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Hardness of Token Swapping on Trees

Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to use the shortest possible sequence of swaps, each of which exchanges the tokens at the two endpoints of an edge of the graph. In parallel token swapping, the goal is to use the fewest rounds, each of which consists of one or more swaps on the edges of a matching. We prove that both of these problems remain NP-hard when the graph is restricted to be a tree. These token swapping problems have been studied by disparate groups of researchers in discrete mathematics, theoretical computer science, robot motion planning, game theory, and engineering. Previous work establishes NP-completeness on general graphs (for both problems); polynomial-time algorithms for simple graph classes such as cliques, stars, paths, and cycles; and constant-factor approximation algorithms in some cases. The two natural cases of sequential and parallel token swapping in trees were first studied over thirty years ago (as "sorting with a transposition tree") and over twenty-five years ago (as "routing permutations via matchings"), yet their complexities were previously unknown. We also show limitations on approximation of sequential token swapping on trees: we identify a broad class of algorithms that encompass all three known polynomial-time algorithms that achieve the best known approximation factor (which is $2$) and show that no such algorithm can achieve an approximation factor less than $2$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Compatible Matchings

A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,n\}$ if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of $n$ points there exists a compatible matching with $\lfloor \sqrt {2n}\rfloor$ edges. More generally, for any $\ell$ labeled point sets we construct compatible matchings of size $Ω(n^{1/\ell})$. As a corresponding upper bound, we use probabilistic arguments to show that for any $\ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has ${\mathcal{O}}(n^{2/({\ell}+1)})$ edges. Finally, we show that $Θ(\log n)$ copies of any set of $n$ points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reconfiguration of Non-crossing Spanning Trees

For a set $P$ of $n$ points in the plane in general position, a non-crossing spanning tree is a spanning tree of the points where every edge is a straight-line segment between a pair of points and no two edges intersect except at a common endpoint. We study the problem of reconfiguring one non-crossing spanning tree of $P$ to another using a sequence of flips where each flip removes one edge and adds one new edge so that the result is again a non-crossing spanning tree of $P$. There is a known upper bound of $2n-4$ flips [Avis and Fukuda, 1996] and a lower bound of $1.5n - 5$ flips. We give a reconfiguration algorithm that uses at most $2n-3$ flips but reduces that to $1.5n-2$ flips when one tree is a path and either: the points are in convex position; or the path is monotone in some direction. For points in convex position, we prove an upper bound of $2d - Ω(\log d)$ where $d$ is half the size of the symmetric difference between the trees. We also examine whether the happy edges (those common to the initial and final trees) need to flip, and we find exact minimum flip distances for small point sets using exhaustive search.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Shooting Stars in Simple Drawings of $K_{m,n}$

Simple drawings are drawings of graphs in which two edges have at most one common point (either a common endpoint, or a proper crossing). It has been an open question whether every simple drawing of a complete bipartite graph $K_{m,n}$ contains a plane spanning tree as a subdrawing. We answer this question to the positive by showing that for every simple drawing of $K_{m,n}$ and for every vertex $v$ in that drawing, the drawing contains a shooting star rooted at $v$, that is, a plane spanning tree containing all edges incident to $v$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is generalized twisted if there is a point $O$ such that every ray emanating from $O$ crosses every edge of the drawing at most once and there is a ray emanating from $O$ which crosses every edge exactly once. Via this new class of simple drawings, we show that every simple drawing of the complete graph with $n$ vertices contains $Ω(n^{\frac{1}{2}})$ pairwise disjoint edges and a plane path of length $Ω(\frac{\log n }{\log \log n})$. Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A superlinear lower bound on the number of 5-holes

Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$-hole in $P$ if $H$ is the vertex set of a convex $5$-gon containing no other points of $P$. For a positive integer $n$, let $h_5(n)$ be the minimum number of 5-holes among all sets of $n$ points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for $h_5(n)$ have been of order $Ω(n)$ and $O(n^2)$, respectively. We show that $h_5(n) = Ω(n\log^{4/5}{n})$, obtaining the first superlinear lower bound on $h_5(n)$. The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set $P$ of points in the plane in general position is partitioned by a line $\ell$ into two subsets, each of size at least 5 and not in convex position, then $\ell$ intersects the convex hull of some 5-hole in $P$. The proof of this result is computer-assisted.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants

A drawing of a graph in the plane is {\it pseudolinear} if the edges of the drawing can be extended to doubly-infinite curves that form an arrangement of pseudolines, that is, any pair of edges crosses precisely once. A special case are {\it rectilinear} drawings where the edges of the graph are drawn as straight line segments. The rectilinear (pseudolinear) crossing number of a graph is the minimum number of pairs of edges of the graph that cross in any of its rectilinear (pseudolinear) drawings. In this paper we describe an ongoing project to continuously obtain better asymptotic upper bounds on the rectilinear and pseudolinear crossing number of the complete graph $K_n$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Drawing Graphs as Spanners

We study the problem of embedding graphs in the plane as good geometric spanners. That is, for a graph $G$, the goal is to construct a straight-line drawing $Γ$ of $G$ in the plane such that, for any two vertices $u$ and $v$ of $G$, the ratio between the minimum length of any path from $u$ to $v$ and the Euclidean distance between $u$ and $v$ is small. The maximum such ratio, over all pairs of vertices of $G$, is the spanning ratio of $Γ$. First, we show that deciding whether a graph admits a straight-line drawing with spanning ratio $1$, a proper straight-line drawing with spanning ratio $1$, and a planar straight-line drawing with spanning ratio $1$ are NP-complete, $\exists \mathbb R$-complete, and linear-time solvable problems, respectively, where a drawing is proper if no two vertices overlap and no edge overlaps a vertex. Second, we show that moving from spanning ratio $1$ to spanning ratio $1+ε$ allows us to draw every graph. Namely, we prove that, for every $ε>0$, every (planar) graph admits a proper (resp. planar) straight-line drawing with spanning ratio smaller than $1+ε$. Third, our drawings with spanning ratio smaller than $1+ε$ have large edge-length ratio, that is, the ratio between the length of the longest edge and the length of the shortest edge is exponential. We show that this is sometimes unavoidable. More generally, we identify having bounded toughness as the criterion that distinguishes graphs that admit straight-line drawings with constant spanning ratio and polynomial edge-length ratio from graphs that require exponential edge-length ratio in any straight-line drawing with constant spanning ratio.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Folding Polyominoes with Holes into a Cube

When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with one or several holes to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special \emph{simple} holes guarantee foldability.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Plane Spanning Trees in Edge-Colored Simple Drawings of $K_n$

Károlyi, Pach, and Tóth proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple drawings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $\lceil (n+5)/6\rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Flips in combinatorial pointed pseudo-triangulations with face degree at most four

In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the flip graph of combinatorial 4-PPTs is connected and has diameter $O(n^2)$, even in the case of labeled vertices with fixed outer face. For this case we provide an $Ω(n\log n)$ lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

New results on lower bounds for the number of (at most k)-facets

In this paper we present three different results dealing with the number of $(\leq k)$-facets of a set of points: 1. We give structural properties of sets in the plane that achieve the optimal lower bound $3\binom{k+2}{2}$ of $(\leq k)$-edges for a fixed $0\leq k\leq \lfloor n/3 \rfloor -1$; 2. We give a simple construction showing that the lower bound $3\binom{k+2}{2}+3\binom{k-\lfloor \frac{n}{3} \rfloor+2}{2}$ for the number of $(\leq k)$-edges of a planar point set appeared in [Aichholzer et al. New lower bounds for the number of ($\leq k$)-edges and the rectilinear crossing number of $K_n$. {\em Disc. Comput. Geom.} 38:1 (2007), 1--14] is optimal in the range $\lfloor n/3 \rfloor \leq k \leq \lfloor 5n/12 \rfloor -1$; 3. We show that for $k < \lfloor n/(d+1) \rfloor$ the number of $(\leq k)$-facets of a set of $n$ points in general position in $\mathbb{R}^d$ is at least $(d+1)\binom{k+d}{d}$, and that this bound is tight in the given range of $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

New lower bounds for the number of $(\leq k)$-edges and the rectilinear crossing number of $K_n$

We provide a new lower bound on the number of $(\leq k)$-edges of a set of $n$ points in the plane in general position. We show that for $0 \leq k \leq\lfloor\frac{n-2}{2}\rfloor$ the number of $(\leq k)$-edges is at least $$ E_k(S) \geq 3\binom{k+2}{2} + \sum_{j=\lfloor\frac{n}{3}\rfloor}^k (3j-n+3), $$ which, for $k\geq \lfloor\tfrac{n}{3}\rfloor$, improves the previous best lower bound in [J. Balogh, G. Salazar, Improved bounds for the number of ($\leq k$)-sets, convex quadrilaterals, and the rectilinear crossing number of $K_n$]. As a main consequence, we obtain a new lower bound on the rectilinear crossing number of the complete graph or, in other words, on the minimum number of convex quadrilaterals determined by $n$ points in the plane in general position. We show that the crossing number is at least $$ \Bigl({41/108}+ε\Bigr) \binom{n}{4} + O(n^3) \geq 0.379631 \binom{n}{4} + O(n^3), $$ which improves the previous bound of $0.37533 \binom{n}{4} + O(n^3)$ in [J. Balogh, G. Salazar, Improved bounds for the number of ($\leq k$)-sets, convex quadrilaterals, and the rectilinear crossing number of $K_n$] and approaches the best known upper bound $0.38058\binom{n}{4}$ in [O. Aichholzer, H. Krasser, Abstract order type extension and new results on the rectilinear crossing number].

0 citations0 reviewsNo code linkedOpen access