Source author record

Benson Joeris

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

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms math.CO

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

A generalization of the Grid Theorem

A graph has tree-width at most $k$ if it can be obtained from a set of graphs each with at most $k+1$ vertices by a sequence of clique sums. We refine this definition by, for each non-negative integer $θ$ , defining the $θ$ -tree-width of a graph to be at most $k$ if it can be obtained from a set of graphs each with at most $k+1$ vertices by a sequence of clique sums on cliques of size less than $θ$ . We find the unavoidable minors for the graphs with large $θ$ -tree-width and we obtain Robertson and Seymour's Grid Theorem as a corollary.

preprint2015arXiv

Geometric Spanning Cycles in Bichromatic Point Sets

Given a set of points in the plane each colored either red or blue, we find non-self-intersecting geometric spanning cycles of the red points and of the blue points such that each edge of the red spanning cycle is crossed at most three times by the blue spanning cycle and vice-versa.

preprint2013arXiv

Simple DFS on the Complement of a Graph and on Partially Complemented Digraphs

A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. A partially complemented digraph $\widetilde{G}$ is a digraph obtained from a sequence of vertex complement operations on $G$ . Dahlhaus et al. showed that, given an adjacency-list representation of $\widetilde{G}$ , depth-first search (DFS) on $G$ can be performed in $O(n + \widetilde{m})$ time, where $n$ is the number of vertices and $\widetilde{m}$ is the number of edges in $\widetilde{G}$ . To achieve this bound, their algorithm makes use of a somewhat complicated stack-like data structure to simulate the recursion stack, instead of implementing it directly as a recursive algorithm. We give a recursive $O(n+\widetilde{m})$ algorithm that uses no complicated data-structures.

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.