Compatible Paths on Labelled Point Sets

Let P and Q be finite point sets of the same cardinality in R2, each labelled from 1 to n. Two noncrossinggeometric graphs GP and GQ spanning P and Q, respectively, are called compatible if for every face f inGP ,there exists a corresponding face in GQ with thesame clockwise ordering of the vertices on its boundaryas in f. In particular, GP and GQ must be straightline embeddings of the same connected n-vertex graphG. No polynomial-time algorithm is known for decidingwhether two labelled point sets admit compatible geometric graphs. The complexity of the problem is open,even when the graphs are constrained to be triangulations, trees, or simple paths.We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios:O(n) time for points in convex position; O(n2) time fortwo simple polygons, where the paths are restricted toremain inside the closed polygons; and O(n2log n) timefor points in general position if the paths are restrictedto be monotone.
info:eu-repo/semantics/published