Reconstruction of the path graph

DOI10.1016/J.COMGEO.2018.02.002MaRDI QIDQ1615670zbMATH OpenOpenAlexFDO

Authors Chaya Keller, Yael Stein

Publication date 31 October 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.00328

zbMATH Keywords

reconstructiongeometric graphsconvex geometric graphsHamiltonian paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Abstract: Let $P$ be a set of $ngeq5$ points in convex position in the plane. The path graph $G(P)$ of $P$ is an abstract graph whose vertices are non-crossing spanning paths of $P$, such that two paths are adjacent if one can be obtained from the other by deleting an edge and adding another edge. We prove that the automorphism group of $G(P)$ is isomorphic to $D_n$, the dihedral group of order $2n$. The heart of the proof is an algorithm that first identifies the vertices of $G(P)$ that correspond to boundary paths of $P$, where the identification is unique up to an automorphism of $K(P)$ as a geometric graph, and then identifies (uniquely) all edges of each path represented by a vertex of $G(P)$. The complexity of the algorithm is $O(NlogN)$ where $N$ is the number of vertices of $G(P)$.

Recommendations

• On the diameter of geometric path graphs of points in convex position
• Hamilton cycles in the path graph of a set of points in convex position
• Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph
• Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees
• Combinatorial reconstruction problems

Cites work

• A quadratic distance bound on sliding between crossing-free spanning trees
• Amortized efficiency of generating planar paths in convex position
• Geometric tree graphs of points in convex position
• Graph reconstruction—a survey
• Hamilton cycles in the path graph of a set of points in convex position
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On planar path transformation
• On the chromatic number of some flip graphs
• On the diameter of geometric path graphs of points in convex position
• Reconstruction of the geometric structure of a set of points in the plane from its geometric tree graph
• Reverse search for enumeration
• Sequences of spanning trees and a fixed tree theorem

Cited in

(2)

• On the diameter of geometric path graphs of points in convex position
• Reconstructing edge-disjoint paths.

This page was built for publication: Reconstruction of the path graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1615670)