Edges and switches, tunnels and bridges

D. Eppstein, M.J. Kreveld, van, E. Mumford, B. Speckmann

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

77 Downloads (Pure)


Edge casing is a well-known method to improve the readability of drawings of non-planar graphs. A cased drawing orders the edges of each edge crossing and interrupts the lower edge in an appropriate neighborhood of the crossing. Certain orders will lead to a more readable drawing than others. We formulate several optimization criteria that try to capture the concept of a "good" cased drawing. Further, we address the algorithmic question of how to turn a given drawing into an optimal cased drawing. For many of the resulting optimization problems, we either find polynomial time algorithms or NP-hardness results.
Originele taal-2Engels
StatusGepubliceerd - 2007
Evenement23rd European Workshop on Computational Geometry (EuroCG 2007) - Graz, Zwitserland
Duur: 19 mrt 200721 mrt 2007
Congresnummer: 23


Workshop23rd European Workshop on Computational Geometry (EuroCG 2007)
Verkorte titelEuroCG


Duik in de onderzoeksthema's van 'Edges and switches, tunnels and bridges'. Samen vormen ze een unieke vingerafdruk.

Citeer dit