15 citations · 73 across the 38 of their papers we have counts for
8 papers · 1 filter
Blind cop-width and balanced minors of graphs
Hector Buffière, Rutger Campbell, Kevin Hendrey +1
We investigate a pursuit-evasion game on an undirected graph in which a robber, moving at a fixed constant speed, attempts to evade a team of cops who are blind to the robber's loc…
Optimal Tree-Decompositions with Bags of Bounded Treewidth
Kevin Hendrey, David R. Wood
We prove that several natural graph classes have tree-decompositions with minimum width such that each bag has bounded treewidth. For example, every planar graph has a tree-decompo…
Embedding Graphs of Simple Treewidth into Sparse Products
Kevin Hendrey, David R. Wood, Jung Hon Yip
We study embeddings of graphs with bounded treewidth or bounded simple treewidth into the undirected graph underlying the directed product of two directed graphs. If the factors ha…
Unavoidable pivot-minors in graphs of large rank-depth
Jungho Ahn, Kevin Hendrey, O-joung Kwon +1
Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer , every graph of sufficiently large rank-d…
Structure of -Matching-Planar Graphs
Kevin Hendrey, Nikolai Karol, David R. Wood
For , we define a simple topological graph (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be…
Polynomial Bounds in the Apex Minor Theorem
Kevin Hendrey, David R. Wood
A graph is "apex" if is planar for some vertex . Eppstein [Algorithmica, 2000] showed that for a minor-closed class , the graphs in …
Short Paths in the Planar Graph Product Structure Theorem
Kevin Hendrey, David R. Wood
The Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM '20] says that every planar graph is contained in for some planar graph wi…
Metric graphs of negative type
Rutger Campbell, Kevin Hendrey, Ben Lund +1
The negative type inequalities of a metric space are closely tied to embeddability. A result by Gupta, Newman, and Rabinovich implies that if a metric graph does not contain a…