BZPEER
More

Discover

About BZPEERSearchGraph

Research tools

HomeCollectionsResearchCollaborationPublish

Network

ExpertsCommunities

Opportunities

Listings

Account

Log inCreate account
Log inCreate account

Source author record

Katie Clinch

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

ResearcherUnclaimed source record
math.CODiscrete Mathematicsmath.MG

Catalog footprint

Research overview

5works
3topics
4close collaborators

Actions

Is this your work?

Log in to claim
Open graphBrowse papers

Published work

5 publications

preprint2022arXiv

Abstract 3-Rigidity and Bivariate C21C_2^1-Splines I: Whiteley's Maximality Conjecture

A conjecture of Graver from 1991 states that the generic 33-dimensional rigidity matroid is the unique maximal abstract 33-rigidity matroid with respect to the weak order on matroids. Based on a close similarity between the generic dd-dimensional rigidity matroid and the generic Cd−2d−1C_{d-2}^{d-1}-cofactor matroid from approximation theory, Whiteley made an analogous conjecture in 1996 that the generic Cd−2d−1C_{d-2}^{d-1}-cofactor matroid is the unique maximal abstract dd-rigidity matroid for all d≥2d\geq 2. We verify the case d=3d=3 of Whiteley's conjecture in this paper. A key step in our proof is to verify a second conjecture of Whiteley that the `double V-replacement operation' preserves independence in the generic C21C_2^1-cofactor matroid.

Open access
preprint2022arXiv

Abstract 3-Rigidity and Bivariate C21C_2^1-Splines II: Combinatorial Characterization

We showed in the first paper of this series that the generic C21C_2^1-cofactor matroid is the unique maximal abstract 33-rigidity matroid. In this paper we obtain a combinatorial characterization of independence in this matroid. This solves the cofactor counterpart of the combinatorial characterization problem for the rigidity of generic 3-dimensional bar-joint frameworks. We use our characterization to verify that the counterparts of conjectures of Dress (on the rank function) and Lovász and Yemini (which suggested a sufficient connectivity condition for rigidity) hold for this matroid.

Open access
preprint2022arXiv

Product structure of graph classes with bounded treewidth

We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the "underlying treewidth" of a graph class G\mathcal{G} to be the minimum non-negative integer cc such that, for some function ff, for every graph G∈G{G \in \mathcal{G}} there is a graph HH with tw(H)≤c{\text{tw}(H) \leq c} such that GG is isomorphic to a subgraph of H⊠Kf(tw(G)){H \boxtimes K_{f(\text{tw}(G))}}. We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth 3; the class of Ks,tK_{s,t}-minor-free graphs has underlying treewidth ss (for t≥max⁡{s,3}{t \geq \max\{s,3\}}); and the class of KtK_t-minor-free graphs has underlying treewidth t−2{t-2}. In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no HH subgraph has bounded underlying treewidth if and only if every component of HH is a subdivided star, and that the class of graphs with no induced HH subgraph has bounded underlying treewidth if and only if every component of HH is a star.

Open access
preprint2016arXiv

Global rigidity of 2-dimensional direction-length frameworks

A 2-dimensional direction-length framework is a collection of points in the plane which are linked by pairwise constraints that fix the direction or length of the line segments joining certain pairs of points. We represent it as a pair (G,p)(G,p), where G=(V;D,L)G=(V;D,L) is a `mixed' graph and p:V→R2p:V\to{\mathbb R}^2 is a point configuration for VV. It is globally rigid if every direction-length framework (G,q)(G,q) which satisfies the same constraints can be obtained from (G,p)(G,p) by a translation or a rotation by 180∘180^\circ. We show that the problem of characterising when a generic framework (G,p)(G,p) is globally rigid can be reduced to the case when GG belongs to a special family of `direction irreducible' mixed graphs, and prove that {every} generic realisation of a direction irreducible mixed graph GG is globally rigid if and only if GG is 2-connected, direction-balanced and redundantly rigid.

Open access
preprint2016arXiv

Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids

A two-dimensional direction-length framework (G,p)(G,p) consists of a multigraph G=(V;D,L)G=(V;D,L) whose edge set is formed of "direction" edges DD and "length" edges LL, and a realisation pp of this graph in the plane. The edges of the framework represent geometric constraints: length edges fix the distance between their endvertices, whereas direction edges specify the gradient of the line through both endvertices. A direction-length framework (G,p)(G,p) is globally rigid if every framework (G,q)(G,q) which satisfies the same direction and length constraints as (G,p)(G,p) can be obtained by translating (G,p)(G,p) in the plane, and/or rotating (G,p)(G,p) by 180∘180^{\circ}. In this paper, we characterise global rigidity for generic direction-length frameworks whose associated rigidity matroid is connected, by showing that such frameworks are globally rigid if and only if every 2-separation of the underlying graph is direction-balanced.

Open access

Research graph

See the researcher in context

Open full explorer

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.