Alternating paths and cycles of minimum length

DOI10.1016/J.COMGEO.2016.07.005MaRDI QIDQ340546zbMATH OpenOpenAlexFDO

Authors W. Evans, Giuseppe Liotta, Henk Meijer, S. Wismath

Publication date 14 November 2016

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2016.07.005

zbMATH Keywords

algorithmalternating paths/cyclescolored pointscycle graphminimal lengthplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

Let \(R\) (red) and \(B\) (blue) be disjoint sets of points in the plane, each containing \(n\) points. An alternating cycle is a cycle graph drawn in the plane with vertex set \(R\cup B\) such that the endpoints of each edge have a different color. An alternating path may also be similarly defined. The length of a cycle or a path is the sum of its edge lengths. Only planar graphs are considered: edges are not allowed to cross. The authors present an algorithm for computing a planar alternating cycle of smallest possible length, in the case when the points of \(R\cup B\) are collinear, in \(\Theta(n\log{n})\) time. This algorithm is modified to compute a planar alternating path of minimal length in \(O(n^2)\) time, again assuming that points are collinear. For the case of 3 disjoint sets of points whose union is collinear, the authors give a \(O(n^2)\) time algorithm for computing a planar alternating cycle of minimum length. In contrast, for any number of disjoint sets that are not collinear, finding the shortest length planar alternating cycle is shown to be NP-hard.

Recommendations

• Alternating paths and cycles of minimum length
• On relative length of longest paths and cycles
• On Hamiltonian alternating cycles and paths
• Cycles and paths in graphs with large minimal degree
• Enumerating minimal length lattice paths
• Transversals of Longest Paths and Cycles
• Cycle lengths and minimum degree of graphs
• Relative length of longest paths and cycles in graphs
• Minimal paths and cycles in set systems
• Minimum-link paths revisited

Cites work

• Bipartite embeddings of trees in the plane
• Drawing colored graphs on colored points
• Drawing colored graphs with constrained vertex positions and few bends per edge
• Embedding planar graphs at fixed vertex locations
• Handbook of graph drawing and visualization
• scientific article; zbMATH DE number 2145233 (Why is no real title available?)
• scientific article; zbMATH DE number 2209732 (Why is no real title available?)
• k-colored Point-set Embeddability of Outerplanar Graphs
• Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations
• ON EMBEDDING A GRAPH ON TWO SETS OF POINTS
• Point-set embeddability of 2-colored trees
• Point-set embeddings of trees with given partial drawings
• Reducibility among combinatorial problems
• SEMI-BALANCED PARTITIONS OF TWO SETS OF POINTS AND EMBEDDINGS OF ROOTED FORESTS
• Simple alternating path problem
• Straight line embeddings of rooted star forests in the plane
• Straight-line embeddings of two rooted trees in the plane
• The Euclidean traveling salesman problem is NP-complete
• Universal point sets for 2-coloured trees

Cited in

(8)

• On Hamiltonian alternating cycles and paths
• On the length of longest alternating paths for multicoloured point sets in convex position
• Geometric planar networks on bichromatic collinear points
• Alternating paths and cycles of minimum length
• ALTERNATING HAMILTON CYCLES WITH MINIMUM NUMBER OF CROSSINGS IN THE PLANE
• 2-colored point-set embeddings of partial 2-trees
• Long Alternating Paths Exist
• Alternating paths along axis-parallel segments

This page was built for publication: Alternating paths and cycles of minimum length

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