Abstrakt. Vi anser att problemet med att rita en uppsättning enkla stigar längs kanterna på en inbäddad underliggande graf G = (V, E), så att det totala antalet korsningar mellan par av stigar minimeras. Detta problem uppstår när man ritar metrokartor, där inbäddningen av G skildrar strukturen i det underliggande nätet, noderna G motsvarar tågstationer, en kant som förbinder två noder innebär att det finns en järnvägslinje som förbinder dem, medan gångarna illustrerar de linjer som förbinder terminalstationer. Vi kallar detta metro-line korsning minimering problem (MLCM). I motsats till problemet med att rita den underliggande grafen snyggt, MLCM har fått mindre uppmärksamhet. Den introducerades nyligen av Benkert et. ............................................................................................................. I detta dokument, som ett första steg mot att lösa MLCM i godtyckliga grafer, studerar vi väg- och trädnätverk. Vi undersöker flera varianter av problemet för vilka vi utvecklar algoritmer för att få optimala lösningar.
Bekos m.fl. REF tog itu med problemet med stigar och träd.
Line crossing minimization on metro maps
{'venue': 'Graph Drawing', 'journal': None, 'mag_field_of_study': ['Computer Science']}