Two Polynomial Time Algorithms for the Metro-line Crossing Minimization Problem

DOI10.1007/978-3-642-00219-9_33MaRDI QIDQ3611868zbMATH OpenOpenAlexFDO

Authors Evmorfia N. Argyriou, Michael A. Bekos, Michael Kaufmann, Antonios Symvonis

Publication date 3 March 2009

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00219-9_33

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• An improved algorithm for the metro-line crossing minimization problem
• Line Crossing Minimization on Metro Maps
• On metro-line crossing minimization
• Metro-line crossing minimization: hardness, approximations, and tractable cases
• Ordering metro lines by block crossings

Cites work

• Graph Drawing
• Graph Drawing
• Introduction to algorithms
• Line Crossing Minimization on Metro Maps
• Minimizing Intra-edge Crossings in Wiring Diagrams and Public Transportation Maps
• Path Simplification for Metro Map Layout

Cited in

(8)

• Edge routing with ordered bundles
• Metro-line crossing minimization: hardness, approximations, and tractable cases
• On metro-line crossing minimization
• An improved algorithm for the metro-line crossing minimization problem
• Minimizing Intra-edge Crossings in Wiring Diagrams and Public Transportation Maps
• Ordering metro lines by block crossings
• Line Crossing Minimization on Metro Maps
• Graph Drawing

This page was built for publication: Two Polynomial Time Algorithms for the Metro-line Crossing Minimization Problem

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