Abstrakt. Ett problem som uppstår i ritningar av transportnät är att minimera antalet korsningar mellan olika transportlinjer. Även om detta kan göras effektivt under särskilda begränsningar, är inte alla lösningar visuellt likvärdiga. Vi föreslår att man slår samman korsningar till blockkorsningar, dvs. korsningar av två angränsande grupper av linjer i följd. Tyvärr, minimera det totala antalet block korsningar är NP-hård även för mycket enkla grafer. Vi ger approximationsalgoritmer för speciella klasser av grafer och en asymptotiskt värsta-fall optimal algoritm för blockkorsningar på allmänna grafer. Det vill säga, vi band antalet block korsningar som vår algoritm behöver och konstruera värsta fall fall där antalet block korsningar som är nödvändigt i någon lösning är asymptotiskt samma som vår bundna.
Fink, Pupyrev och Wolff Ref föreslår att en linje korsas i korsningar av block av linjer minimerar antalet block korsningar på kartan.
Ordering Metro Lines by Block Crossings
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}