skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, February 13 until 2:00 AM ET on Friday, February 14 due to maintenance. We apologize for the inconvenience.


Title: Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees
Let P be a set of n points in the plane in general position. The order type of P specifies, for every ordered triple, a positive or negative orientation; and the x-type (a.k.a. crossing type) of P specifies, for every unordered 4-tuple, whether they are in convex position. Geometric algorithms on P typically rely on primitives involving the order type or x-type (i.e., triples or 4-tuples). In this paper, we show that the x-type of P can be reconstructed from the compatible exchange graph G1(P) of noncrossing spanning trees on P. This extends a recent result by Keller and Perles (2016), who proved that the x-type of P can be reconstructed from the exchange graph G0(P) of noncrossing spanning trees, where G1(P) is a subgraph of G0(P) . A crucial ingredient of our proof is a structure theorem on the maximal sets of pairwise noncrossing edges (msnes) between two components of a planar straight-line graph on the point set P.  more » « less
Award ID(s):
1423615
PAR ID:
10097780
Author(s) / Creator(s):
Date Published:
Journal Name:
International Conference on Discrete Geometry for Computer Imagery
Volume:
11414
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Mestre, Julián ; Wirth, Anthony (Ed.)
    For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in O(n log n) time where n is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of O(√n). It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an O(log n)-factor approximation algorithm for the general case. 
    more » « less
  2. The force response of cardiac muscle undergoing a quick stretch is conventionally interpreted to represent stretching of attached myosin crossbridges (phase 1) and detachment of these stretched crossbridges at an exponential rate (phase 2), followed by crossbridges reattaching in increased numbers due to an enhanced activation of the thin filament (phases 3 and 4). We propose that, at least in mammalian cardiac muscle, phase 2 instead represents an enhanced detachment rate of myosin crossbridges due to stretch, phase 3 represents the reattachment of those same crossbridges, and phase 4 is a passive-like viscoelastic response with power-law relaxation. To test this idea, we developed a two-state model of crossbridge attachment and detachment. Unitary force was assigned when a crossbridge was attached, and an elastic force was generated when an attached crossbridge was displaced. Attachment rate, f(x), was spatially distributed with a total magnitude f0. Detachment rate was modeled as g(x) = g0+ g1x, where g0 is a constant and g1 indicates sensitivity to displacement. The analytical solution suggested that the exponential decay rate of phase 2 represents (f0 + g0) and the exponential rise rate of phase 3 represents g0. The depth of the nadir between phases 2 and 3 is proportional to g1. We prepared skinned mouse myocardium and applied a 1% stretch under varying concentrations of inorganic phosphate (Pi). The resulting force responses fitted the analytical solution well. The interpretations of phases 2 and 3 were consistent with lower f0 and higher g0 with increasing Pi. This novel scheme of interpreting the force response to a quick stretch does not require enhanced thin-filament activation and suggests that the myosin detachment rate is sensitive to stretch. Furthermore, the enhanced detachment rate is likely not due to the typical detachment mechanism following MgATP binding, but rather before MgADP release, and may involve reversal of the myosin power stroke.

     
    more » « less
  3. Abstract

    The discrete Green's functions are the pseudoinverse (or the inverse) of the Laplacian (or its variations) of a graph. In this article, we will give combinatorial interpretations of Green's functions in terms of enumerating trees and forests in a graph that will be used to derive further formulas for several graph invariants. For example, we show that the trace of the Green's function associated with the combinatorial Laplacian of a connected simple graph on vertices satisfieswhere denotes the eigenvalues of the combinatorial Laplacian, denotes the number of spanning trees, and denotes the set of rooted spanning 2‐forests in . We will prove forest formulas for discrete Green's functions for directed and weighted graphs and apply them to study random walks on graphs and digraphs. We derive a forest expression of the hitting time for digraphs, which gives combinatorial proofs to old and new results about hitting times, traces of discrete Green's functions, and other related quantities.

     
    more » « less
  4. The noncrossing partition poset associated to a Coxeter group $W$ and Coxeter element $c$ is the interval $[1,c]_T$ in the absolute order on $W$. We construct a new model of noncrossing partititions for $W$ of classical affine type, using planar diagrams. The model in type $\afftype{A}$ consists of noncrossing partitions of an annulus. In type~$\afftype{C}$, the model consists of symmetric noncrossing partitions of an annulus or noncrossing partitions of a disk with two orbifold points. Following the lead of McCammond and Sulway, we complete $[1,c]_T$ to a lattice by factoring the translations in $[1,c]_T$, but the combinatorics of the planar diagrams leads us to make different choices about how to factor. 
    more » « less
  5. Abstract

    A graph is ‐freeif it has no induced subgraph isomorphic to , and |G| denotes the number of vertices of . A conjecture of Conlon, Sudakov and the second author asserts that:

    For every graph , there exists such that in every ‐free graph with |G| there are two disjoint sets of vertices, of sizes at least and , complete or anticomplete to each other.

    This is equivalent to:

    The “sparse linear conjecture”: For every graph , there exists such that in every ‐free graph with , either some vertex has degree at least , or there are two disjoint sets of vertices, of sizes at least and , anticomplete to each other.

    We prove a number of partial results toward the sparse linear conjecture. In particular, we prove it holds for a large class of graphs , and we prove that something like it holds for all graphs . More exactly, say is “almost‐bipartite” if is triangle‐free and can be partitioned into a stable set and a set inducing a graph of maximum degree at most one. (This includes all graphs that arise from another graph by subdividing every edge at least once.) Our main result is:

    The sparse linear conjecture holds for all almost‐bipartite graphs .

    (It remains open when is the triangle .) There is also a stronger theorem:

    For every almost‐bipartite graph , there exist such that for every graph with and maximum degree less than , and for every with , either contains induced copies of , or there are two disjoint sets with and , and with at most edges between them.

    We also prove some variations on the sparse linear conjecture, such as:

    For every graph , there exists such that in every ‐free graph with vertices, either some vertex has degree at least , or there are two disjoint sets of vertices with , anticomplete to each other.

     
    more » « less