Problemet med bankorsningsminimering (MLCM) infördes nyligen [5] som ett svar på problemet med att rita metrokartor eller allmänna transportnät i allmänhet. Enligt detta problem får vi en planar, inbäddad graf G = (V, E) och en uppsättning L enkla vägar på G, kallas linjer. Huvuduppgiften är att placera linjerna på inbäddningen av G, så att antalet korsningar mellan par av linjer minimeras. Vårt viktigaste bidrag är två polynomalgoritmer. Den första löser det allmänna fallet av MLCM-problemet, där de linjer som passerar en viss vertex av G tillåts använda någon sida av det för att antingen "in" eller "exit", förutsatt att slutpunkterna för linjerna är belägna på hörn av grad 1. Den andra -som är mer effektiv när det gäller tids komplexitet - löser det begränsade fallet, där endast vänster och höger sida av varje vertex kan användas. Såvitt vi vet är detta första gången som det allmänna fallet med MLCM-problemet är löst. Tidigare arbete i grafritningslitteraturen ägnades åt det begränsade fallet av MLCM-problemet under det ytterligare antagandet att slutpunkterna för linjerna antingen är de översta eller de lägsta i deras motsvarande hörn, dvs. de är antingen på toppen eller under de linjer som passerar genom vertex. Även i detta fall förbättrar vi ett känt resultat av Asquith et al. [3] från O( ska vara 5/2 och L ska vara 3 ) till O(-V) (-)(-)(-)(-) + -(-)).
Tidningen om metro-line korsning minimering problem av Argyriou et al. REF inspirerade oss att använda tekniken för metro-linjer korsning minimering för att minimera kantkorsningar inuti buntarna.
Two Polynomial Time Algorithms for the Metro-line Crossing Minimization Problem
{'venue': 'Graph Drawing', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}