BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Birgit Vogtenhuber

Birgit Vogtenhuber appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational Geometrymath.CODiscrete MathematicsData Structures and AlgorithmsComputational ComplexityRobotics

Catalog footprint

What is connected

23works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

23 published item(s)

preprint2022arXiv

Coloring circle arrangements: New $4$-chromatic planar graphs

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most $3$. Motivated by this conjecture, we study the colorability of arrangement graphs for different classes of arrangements of (pseudo-)circles. In this paper the conjecture is verified for $\triangle$-saturated pseudocircle arrangements, i.e., for arrangements where one color class of the 2-coloring of faces consists of triangles only, as well as for further classes of (pseudo-)circle arrangements. These results are complemented by a construction which maps $\triangle$-saturated arrangements with a pentagonal face to arrangements with 4-chromatic 4-regular arrangement graphs. This "corona" construction has similarities with the crowning construction introduced by Koester (1985). Based on exhaustive experiments with small arrangements we propose three strengthenings of the original conjecture. We also investigate fractional colorings. It is shown that the arrangement graph of every arrangement $\mathcal{A}$ of pairwise intersecting pseudocircles is "close" to being $3$-colorable. More precisely, the fractional chromatic number $χ_f(\mathcal{A})$ of the arrangement graph is bounded from above by $χ_f(\mathcal{A}) \le 3+O(\frac{1}{n})$, where $n$ is the number of pseudocircles of $\mathcal{A}$. Furthermore, we construct an infinite family of $4$-edge-critical $4$-regular planar graphs which are fractionally $3$-colorable. This disproves a conjecture of Gimbel, Kündgen, Li, and Thomassen (2019).

0 citations0 reviewsNo code linkedOpen access
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

Empty Triangles in Generalized Twisted Drawings of $K_n$

Simple drawings are drawings of graphs in the plane or on the sphere such that vertices are distinct points, edges are Jordan arcs connecting their endpoints, and edges intersect at most once (either in a proper crossing or in a shared endpoint). Simple drawings are 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. We show that all generalized twisted drawings of $K_n$ contain exactly $2n-4$ empty triangles, by this making a substantial step towards proving the conjecture that this is the case for every simple drawing of $K_n$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Inserting one edge into a simple drawing is hard

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 $σ$, it can be decided in polynomial time whether there exists a pseudocircle $Φ_σ$ extending $σ$ for which $\mathcal{A}\cup\{Φ_σ\}$ is again an arrangement of pseudocircles.

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

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

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

Minimizing The Maximum Distance Traveled To Form Patterns With Systems of Mobile Robots

In the pattern formation problem, robots in a system must self-coordinate to form a given pattern, regardless of translation, rotation, uniform-scaling, and/or reflection. In other words, a valid final configuration of the system is a formation that is \textit{similar} to the desired pattern. While there has been no shortage of research in the pattern formation problem under a variety of assumptions, models, and contexts, we consider the additional constraint that the maximum distance traveled among all robots in the system is minimum. Existing work in pattern formation and closely related problems are typically application-specific or not concerned with optimality (but rather feasibility). We show the necessary conditions any optimal solution must satisfy and present a solution for systems of three robots. Our work also led to an interesting result that has applications beyond pattern formation. Namely, a metric for comparing two triangles where a distance of $0$ indicates the triangles are similar, and $1$ indicates they are \emph{fully dissimilar}.

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
preprint2016arXiv

Intersection Graphs of Rays and Grounded Segments

We consider several classes of intersection graphs of line segments in the plane and prove new equality and separation results between those classes. In particular, we show that: (1) intersection graphs of grounded segments and intersection graphs of downward rays form the same graph class, (2) not every intersection graph of rays is an intersection graph of downward rays, and (3) not every intersection graph of rays is an outer segment graph. The first result answers an open problem posed by Cabello and Jejčič. The third result confirms a conjecture by Cabello. We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs. We further characterize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs. We prove that these recognition problems are complete for the existential theory of the reals. This holds even if a 1-string realization is given as additional input.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Modem Illumination of Monotone Polygons

We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number $k$ of walls. We call these objects $k$-modems and study the minimum number of $k$-modems sufficient and sometimes necessary to illuminate monotone and monotone orthogonal polygons. We show that every monotone polygon with $n$ vertices can be illuminated with $\big\lceil \frac{n-2}{2k+3} \big\rceil$ $k$-modems. In addition, we exhibit examples of monotone polygons requiring at least $\lceil \frac {n-2} {2k+3}\rceil$ $k$-modems to be illuminated. For monotone orthogonal polygons with $n$ vertices we show that for $k=1$ and for even $k$, every such polygon can be illuminated with $\big\lceil \frac{n-2}{2k+4} \big\rceil$ $k$-modems, while for odd $k\geq3$, $\big\lceil \frac{n-2}{2k+6} \big\rceil$ $k$-modems are always sufficient. Further, by presenting according examples of monotone orthogonal polygons, we show that both bounds are tight.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Representing Directed Trees as Straight Skeletons

The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

$(n,m)$-Fold Covers of Spheres

A well known consequence of the Borsuk-Ulam theorem is that if the $d$-dimensional sphere $S^d$ is covered with less than $d+2$ open sets, then there is a set containing a pair of antipodal points. In this paper we provide lower and upper bounds on the minimum number of open sets, not containing a pair of antipodal points, needed to cover the $d$-dimensional sphere $n$ times, with the additional property that the northern hemisphere is covered $m > n$ times. We prove that if the open northern hemisphere is to be covered $m$ times then at least $ \lceil \frac{d-1}{2} \rceil+n+m$ and at most $d+n+m$ sets are needed. For the case of $n=1$ and $d \ge 2$, this number is equal to $d+2$ if $m \le \lfloor \frac{d}{2} \rfloor + 1$ and equal to $ \lfloor \frac{d-1}{2} \rfloor + 2 +m$ if $m > \lfloor \frac{d}{2} \rfloor + 1$. If the closed northern hemisphere is to be covered $m$ times then $d+2m-1$ sets are needed, this number is also sufficient. We also present results on a related problem of independent interest. We prove that if $S^d$ is covered $n$ times with open sets, not containing a pair of antipodal points, then there exists a point that is covered at least $ \lceil \frac{d}{2} \rceil +n$ times. Furthermore, we show that there are covers in which no point is covered more than $n+d$ times.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Embedding Four-directional Paths on Convex Point Sets

A directed path whose edges are assigned labels "up", "down", "right", or "left" is called \emph{four-directional}, and \emph{three-directional} if at most three out of the four labels are used. A \emph{direction-consistent embedding} of an \mbox{$n$-vertex} four-directional path $P$ on a set $S$ of $n$ points in the plane is a straight-line drawing of $P$ where each vertex of $P$ is mapped to a distinct point of $S$ and every edge points to the direction specified by its label. We study planar direction-consistent embeddings of three- and four-directional paths and provide a complete picture of the problem for convex point sets.

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
preprint2014arXiv

Monotone Simultaneous Embedding of Directed Paths

We study monotone simultaneous embeddings of upward planar digraphs, which are simultaneous embeddings where the drawing of each digraph is upward planar, and the directions of the upwardness of different graphs can differ. We first consider the special case where each digraph is a directed path. In contrast to the known result that any two directed paths admit a monotone simultaneous embedding, there exist examples of three paths that do not admit such an embedding for any possible choice of directions of monotonicity. We prove that if a monotone simultaneous embedding of three paths exists then it also exists for any possible choice of directions of monotonicity. We provide a polynomial-time algorithm that, given three paths, decides whether a monotone simultaneous embedding exists and, in the case of existence, also constructs such an embedding. On the other hand, we show that already for three paths, any monotone simultaneous embedding might need a grid of exponential (w.r.t. the number of vertices) size. For more than three paths, we present a polynomial-time algorithm that, given any number of paths and predefined directions of monotonicity, decides whether the paths admit a monotone simultaneous embedding with respect to the given directions, including the construction of a solution if it exists. Further, we show several implications of our results on monotone simultaneous embeddings of general upward planar digraphs. Finally, we discuss complexity issues related to our problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On $k$-Gons and $k$-Holes in Point Sets

We consider a variation of the classical Erdős-Szekeres problems on the existence and number of convex $k$-gons and $k$-holes (empty $k$-gons) in a set of $n$ points in the plane. Allowing the $k$-gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any $k$ and sufficiently large $n$, we give a quadratic lower bound for the number of $k$-holes, and show that this number is maximized by sets in convex position.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Empty triangles in good drawings of the complete graph

A good drawing of a simple graph is a drawing on the sphere or, equivalently, in the plane in which vertices are drawn as distinct points, edges are drawn as Jordan arcs connecting their end vertices, and any pair of edges intersects at most once. In any good drawing, the edges of three pairwise connected vertices form a Jordan curve which we call a triangle. We say that a triangle is empty if one of the two connected components it induces does not contain any of the remaining vertices of the drawing of the graph. We show that the number of empty triangles in any good drawing of the complete graph $K_n$ with $n$ vertices is at least $n$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Geodesic-Preserving Polygon Simplification

Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon $\mathcal{P}$ by a polygon $\mathcal{P}'$ such that (1) $\mathcal{P}'$ contains $\mathcal{P}$, (2) $\mathcal{P}'$ has its reflex vertices at the same positions as $\mathcal{P}$, and (3) the number of vertices of $\mathcal{P}'$ is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both $\mathcal{P}$ and $\mathcal{P}'$, our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of $\mathcal{P}$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Linear transformation distance for bichromatic matchings

Let $P=B\cup R$ be a set of $2n$ points in general position, where $B$ is a set of $n$ blue points and $R$ a set of $n$ red points. A \emph{$BR$-matching} is a plane geometric perfect matching on $P$ such that each edge has one red endpoint and one blue endpoint. Two $BR$-matchings are compatible if their union is also plane. The \emph{transformation graph of $BR$-matchings} contains one node for each $BR$-matching and an edge joining two such nodes if and only if the corresponding two $BR$-matchings are compatible. In SoCG 2013 it has been shown by Aloupis, Barba, Langerman, and Souvaine that this transformation graph is always connected, but its diameter remained an open question. In this paper we provide an alternative proof for the connectivity of the transformation graph and prove an upper bound of $2n$ for its diameter, which is asymptotically tight.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Maximizing Maximal Angles for Plane Straight-Line Graphs

Let $G=(S, E)$ be a plane straight-line graph on a finite point set $S\subset\R^2$ in general position. The incident angles of a vertex $p \in S$ of $G$ are the angles between any two edges of $G$ that appear consecutively in the circular order of the edges incident to $p$. A plane straight-line graph is called $ϕ$-open if each vertex has an incident angle of size at least $ϕ$. In this paper we study the following type of question: What is the maximum angle $ϕ$ such that for any finite set $S\subset\R^2$ of points in general position we can find a graph from a certain class of graphs on $S$ that is $ϕ$-open? In particular, we consider the classes of triangulations, spanning trees, and paths on $S$ and give tight bounds in most cases.

0 citations0 reviewsNo code linkedOpen access