Alternating paths and cycles of minimum length

DOI10.1016/j.comgeo.2016.07.005zbMath1359.65033OpenAlexW2479238111MaRDI QIDQ340546

Giuseppe Liotta, William S. Evans, Stephen K. Wismath, Henk G. Meijer

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)

Related Items

Geometric planar networks on bichromatic collinear points, 2-colored point-set embeddings of partial 2-trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal point sets for 2-coloured trees
• Simple alternating path problem
• Point-set embeddings of trees with given partial drawings
• Drawing colored graphs on colored points
• Drawing colored graphs with constrained vertex positions and few bends per edge
• The Euclidean traveling salesman problem is NP-complete
• Straight-line embeddings of two rooted trees in the plane
• Bipartite embeddings of trees in the plane
• Straight line embeddings of rooted star forests in the plane
• Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations
• Point-Set Embeddability of 2-Colored Trees
• Reducibility among Combinatorial Problems
• k-colored Point-set Embeddability of Outerplanar Graphs
• ON EMBEDDING A GRAPH ON TWO SETS OF POINTS
• SEMI-BALANCED PARTITIONS OF TWO SETS OF POINTS AND EMBEDDINGS OF ROOTED FORESTS
• Embedding planar graphs at fixed vertex locations