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

algorithmplanar graphminimal lengthalternating paths/cyclescolored pointscycle graph

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 2145233 (Why is no real title available?)
• scientific article; zbMATH DE number 2209732 (Why is no real title available?)
• 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
• 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
• k-colored Point-set Embeddability of Outerplanar Graphs

Cited in

(8)

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

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)