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

Therese Biedl

Therese Biedl contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryData Structures and AlgorithmsDiscrete Mathematicsmath.COComputational Complexity

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
11works
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

11 published item(s)

preprint2026arXiv

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs

In this paper, we study the dominating set problem in \emph{RDV graphs}, a graph class that lies between interval graphs and chordal graphs and is defined as the \textbf{v}ertex-intersection graphs of \textbf{d}ownward paths in a \textbf{r}ooted tree. It was shown in a previous paper that adjacency queries in an RDV graph can be reduced to the question whether a horizontal segment intersects a vertical segment. This was then used to find a maximum matching in an $n$-vertex RDV graph, using priority search trees, in $O(n\log n)$ time, i.e., without even looking at all edges. In this paper, we show that if additionally we also use a ray shooting data structure, we can also find a minimum dominating set in an RDV graph $O(n\log n)$ time (presuming a linear-sized representation of the graph is given). The same idea can also be used for a new proof to find a minimum dominating set in an interval graph in $O(n)$ time.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Large Matchings in Maximal 1-planar graphs

It is well-known that every maximal planar graph has a matching of size at least $\tfrac{n+8}{3}$ if $n\geq 14$. In this paper, we investigate similar matching-bounds for maximal \emph{1-planar} graphs, i.e., graphs that can be drawn such that every edge has at most one crossing. In particular we show that every 3-connected simple-maximal 1-planar graph has a matching of size at least $\tfrac{2n+6}{5}$; the bound decreases to $\tfrac{3n+14}{10}$ if the graph need not be 3-connected. We also give (weaker) bounds when the graph comes with a fixed 1-planar drawing or is not simple. All our bounds are tight in the sense that some graph that satisfies the restrictions has no bigger matching.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

On the complexity of embedding in graph products

Graph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph $G$ in a host graph that is the strong product of a path $P$ with a graph $H$ that satisfies some properties, such as having small treewidth, pathwidth or tree depth. We show that this is NP-hard, even under numerous restrictions on both $G$ and $H$. In particular, computing the row pathwidth and the row treedepth is NP-hard even for a tree of small pathwidth, while computing the row treewidth is NP-hard even for series-parallel graphs.

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
preprint2020arXiv

Building a larger class of graphs for efficient reconfiguration of vertex colouring

A $k$-colouring of a graph $G$ is an assignment of at most $k$ colours to the vertices of $G$ so that adjacent vertices are assigned different colours. The reconfiguration graph of the $k$-colourings, $\mathcal{R}_k(G)$, is the graph whose vertices are the $k$-colourings of $G$ and two colourings are joined by an edge in $\mathcal{R}_k(G)$ if they differ in colour on exactly one vertex. For a $k$-colourable graph $G$, we investigate the connectivity and diameter of $\mathcal{R}_{k+1}(G)$. It is known that not all weakly chordal graphs have the property that $\mathcal{R}_{k+1}(G)$ is connected. On the other hand, $\mathcal{R}_{k+1}(G)$ is connected and of diameter $O(n^2)$ for several subclasses of weakly chordal graphs such as chordal, chordal bipartite, and $P_4$-free graphs. We introduce a new class of graphs called OAT graphs that extends the latter classes and in fact extends outside the class of weakly chordal graphs. OAT graphs are built from four simple operations, disjoint union, join, and the addition of a clique or comparable vertex. We prove that if $G$ is a $k$-colourable OAT graph then $\mathcal{R}_{k+1}(G)$ is connected with diameter $O(n^2)$. Furthermore, we give polynomial time algorithms to recognize OAT graphs and to find a path between any two colourings in $\mathcal{R}_{k+1}(G)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Drawing Halin-graphs with small height

In this paper, we study how to draw Halin-graphs, i.e., planar graphs that consist of a tree $T$ and a cycle among the leaves of that tree. Based on tree-drawing algorithms and the pathwidth $ pw(T) $, a well-known graph parameter, we find poly-line drawings of height at most $6pw(T)+3\in O(\log n)$. We also give an algorithm for straight-line drawings, and achieve height at most $12pw(T)+1$ for Halin-graphs, and smaller if the Halin-graph is cubic. We show that the height achieved by our algorithms is optimal in the worst case (i.e. for some Halin-graphs).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Drawing outer-1-planar graphs revisited

In a recent article (Auer et al, Algorithmica 2016) it was claimed that every outer-1-planar graph has a planar visibility representation of area $O(n\log n)$. In this paper, we show that this is wrong: There are outer-1-planar graphs that require $Ω(n^2)$ area in any planar drawing. Then wegive a construction (using crossings, but preserving a given outer-1-planar embedding) that results in an orthogonal box-drawing with O(n log n) area and at most two bends per edge.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding large matchings in 1-planar graphs of minimum degree 3

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Matchings in 1-planar graphs with large minimum degree

In 1979, Nishizeki and Baybars showed that every planar graph with minimum degree 3 has a matching of size $\frac{n}{3}+c$ (where the constant $c$ depends on the connectivity), and even better bounds hold for planar graphs with minimum degree 4 and 5. In this paper, we investigate similar matching-bounds for {\em 1-planar} graphs, i.e., graphs that can be drawn such that every edge has at most one crossing. We show that every 1-planar graph with minimum degree 3 has a matching of size at least $\frac{1}{7}n+\frac{12}{7}$, and this is tight for some graphs. We provide similar bounds for 1-planar graphs with minimum degree 4 and 5, while the case of minimum degree 6 and 7 remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Layered Fan-Planar Graph Drawings

In this paper, we study fan-planar drawings that use $h$ layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence of such drawings is fixed-parameter tractable in $h$, via a reduction to a similar result for planar graphs by Dujmović et al. If the embedding is not fixed, then we give partial results for $h=2$: It was already known how to test existence of fan-planar proper 2-layer drawings for 2-connected graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting results for graphs with a fan-planar proper $h$-layer drawings; in particular we bound their pathwidth and show that they have a bar-1-visibility representation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reconstructing a Polyhedron between Polygons in Parallel Slices

Given two $n$-vertex polygons, $P=(p_1, \ldots, p_n)$ lying in the $xy$-plane at $z=0$, and $P'=(p'_1, \ldots, p'_n)$ lying in the $xy$-plane at $z=1$, a banded surface is a triangulated surface homeomorphic to an annulus connecting $P$ and $P'$ such that the triangulation's edge set contains vertex disjoint paths $π_i$ connecting $p_i$ to $p'_i$ for all $i =1, \ldots, n$. The surface then consists of bands, where the $i$th band goes between $π_i$ and $π_{i+1}$. We give a polynomial-time algorithm to find a banded surface without Steiner points if one exists. We explore connections between banded surfaces and linear morphs, where time in the morph corresponds to the $z$ direction. In particular, we show that if $P$ and $P'$ are convex and the linear morph from $P$ to $P'$ (which moves the $i$th vertex on a straight line from $p_i$ to $p'_i$) remains planar at all times, then there is a banded surface without Steiner points.

0 citations0 reviewsNo code linkedOpen access