Source author record

Owen Merkel

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

ResearcherUnclaimed source record

Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

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)$ .

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.

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.