Source author record

Torrie L. Nichols

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

ResearcherUnclaimed source record

Computational Geometry math.CO

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Transition Operations over Plane Trees

The operation of transforming one spanning tree into another by replacing an edge has been considered widely, both for general and planar straight-line graphs. For the latter, several variants have been studied (e.g., edge slides and edge rotations). In a transition graph on the set $\mathcal{T}(S)$ of noncrossing straight-line spanning trees on a finite point set $S$ in the plane, two spanning trees are connected by an edge if one can be transformed into the other by such an operation. We study bounds on the diameter of these graphs, and consider the various operations on point sets in both general position and convex position. In addition, we address variants of the problem where operations may be performed simultaneously or the edges are labeled. We prove new lower and upper bounds for the diameters of the corresponding transition graphs and pose open problems.

preprint2016arXiv

Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs

We consider edge insertion and deletion operations that increase the connectivity of a given planar straight-line graph (PSLG), while minimizing the total edge length of the output. We show that every connected PSLG $G=(V,E)$ in general position can be augmented to a 2-connected PSLG $(V,E\cup E^+)$ by adding new edges of total Euclidean length $\|E^+\|\leq 2\|E\|$ , and this bound is the best possible. An optimal edge set $E^+$ can be computed in $O(|V|^4)$ time; however the problem becomes NP-hard when $G$ is disconnected. Further, there is a sequence of edge insertions and deletions that transforms a connected PSLG $G=(V,E)$ into a planar straight-line cycle $G'=(V,E')$ such that $\|E'\|\leq 2\|{\rm MST}(V)\|$ , and the graph remains connected with edge length below $\|E\|+\|{\rm MST}(V)\|$ at all stages. These bounds are the best possible.

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.