Source author record

Paul Jungeblut

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

ResearcherUnclaimed source record

math.CO Computational Geometry Computational Complexity Data Structures and Algorithms Discrete Mathematics

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Recognizing Unit Disk Graphs in Hyperbolic Geometry is $\exists\mathbb{R}$ -Complete

A graph G is a (Euclidean) unit disk graph if it is the intersection graph of unit disks in the Euclidean plane $\mathbb{R}^2$ . Recognizing them is known to be $\exists\mathbb{R}$ -complete, i.e., as hard as solving a system of polynomial inequalities. In this note we describe a simple framework to translate $\exists\mathbb{R}$ -hardness reductions from the Euclidean plane $\mathbb{R}^2$ to the hyperbolic plane $\mathbb{H}^2$ . We apply our framework to prove that the recognition of unit disk graphs in the hyperbolic plane is also $\exists\mathbb{R}$ -complete.

preprint2022arXiv

Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence 3-edge-colorable. We provide an efficient recognition algorithm that given an $n$ -vertex planar graph, augments this graph in $O(n^2)$ steps to a planar cubic bridgeless supergraph, or decides that no such augmentation is possible. The main tools involve the Generalized Antifactor-problem for the fixed embedding case, and SPQR-trees for the variable embedding case.

preprint2022arXiv

The Complexity of the Hausdorff Distance

We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algebraic sets is bounded by a given threshold is complete for the complexity class $\forall\exists_<\mathbb{R}$ . This implies that the problem is NP-, co-NP-, $\exists\mathbb{R}$ - and $\forall\mathbb{R}$ -hard.

preprint2022arXiv

The product structure of squaregraphs

A squaregraph is a plane graph in which each internal face is a $4$ -cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semi-strong product of an outerplanar graph and a path. We generalise this result for infinite squaregraphs, and show that this is best possible in the sense that "outerplanar graph" cannot be replaced by "forest".

preprint2020arXiv

Guarding Quadrangulations and Stacked Triangulations with Edges

Let $G = (V,E)$ be a plane graph. A face $f$ of $G$ is guarded by an edge $vw \in E$ if at least one vertex from $\{v,w\}$ is on the boundary of $f$ . For a planar graph class $\mathcal{G}$ we ask for the minimal number of edges needed to guard all faces of any $n$ -vertex graph in $\mathcal{G}$ . We prove that $\lfloor n/3 \rfloor$ edges are always sufficient for quadrangulations and give a construction where $\lfloor (n-2)/4 \rfloor$ edges are necessary. For $2$ -degenerate quadrangulations we improve this to a tight upper bound of $\lfloor n/4 \rfloor$ edges. We further prove that $\lfloor 2n/7 \rfloor$ edges are always sufficient for stacked triangulations (that are the $3$ -degenerate triangulations) and show that this is best possible up to a small additive constant.

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.

Paul Jungeblut

Research overview

Is this your work?

5 publications

Recognizing Unit Disk Graphs in Hyperbolic Geometry is $\exists\mathbb{R}$ -Complete

Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

The Complexity of the Hausdorff Distance

The product structure of squaregraphs

Guarding Quadrangulations and Stacked Triangulations with Edges

See the researcher in context

Building this map preview

Paul Jungeblut

Research overview

Is this your work?

5 publications

Recognizing Unit Disk Graphs in Hyperbolic Geometry is ∃R\exists\mathbb{R}∃R-Complete

Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs

The Complexity of the Hausdorff Distance

The product structure of squaregraphs

Guarding Quadrangulations and Stacked Triangulations with Edges

See the researcher in context

Building this map preview

Recognizing Unit Disk Graphs in Hyperbolic Geometry is $\exists\mathbb{R}$ -Complete