Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees

DOI10.1016/j.ipl.2021.106116OpenAlexW3145243131MaRDI QIDQ2032154

Csaba D. Tóth, Marcos Oropeza

Publication date: 16 June 2021

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2021.106116

zbMATH Keywords

spanning treecomputational geometryreconfigurationcrossing type

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph
• On \(\leq k\)-edges, crossings, and halving lines of geometric drawings of \(K _{n }\)
• A quadratic distance bound on sliding between crossing-free spanning trees
• The complexity of point configurations
• Axioms and hulls
• Analytic combinatorics of non-crossing configurations
• Computing minimum length paths of a given homotopy class
• Testing homotopy for paths in the plane
• Order on order types
• Reverse search for enumeration
• On the number of plane geometric graphs
• Computing the flip distance between triangulations
• Computing homotopic shortest paths efficiently
• Flip distance between triangulations of a planar point set is APX-hard
• Encompassing colored planar straight line graphs
• Counting Plane Graphs: Flippability and Its Applications
• The Rectilinear Crossing Number of K n : Closing in (or Are We?)
• Subquadratic encodings for point configurations
• An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings
• The Complexity of Order Type Isomorphism
• Graph-Theoretic Concepts in Computer Science
• Enumeration of simple complete topological graphs
• Transition operations over plane trees

This page was built for publication: Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees