Abstrakt. En viktig faktor som påverkar läsbarheten av en grafritning är dess upplösning. I grafritningslitteraturen mäts antingen upplösningen av en ritning baserat på de vinklar som bildas av på varandra följande kanter vid en gemensam nod (angulär upplösning) eller de vinklar som bildas vid kantkorsningar (korsupplösning). I detta dokument utvärderar vi både genom att införa begreppet "total upplösning", det vill säga det minsta av vinkel- och korsningsupplösningen. Såvitt vi vet är detta första gången som problemet med att maximera den totala upplösningen av en ritning studeras. Papperets huvudsakliga bidrag består av ritningar av asymptotiskt optimal total upplösning för kompletta grafer (cirkulära ritningar) och för fullständiga bipartitgrafer (2-skiktsritningar). Dessutom presenterar och experimentellt utvärderar vi en kraftriktad algoritm som konstruerar ritningar av stor totalupplösning.
Argyriou m.fl. REF studerade en generalisering av kors- och vinkelupplösningens maximeringsproblem, där de minsta av dessa storheter maximeras och presenterade optimala algoritmer för kompletta grafer och en kraftriktad algoritm för allmänna grafer.
Maximizing the Total Resolution of Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}