Edges and switches,tunnels and bridges |
| |
Authors: | David Eppstein Marc van Kreveld Elena Mumford Bettina Speckmann |
| |
Institution: | 1. Department of Computer Science, University of California, Irvine, USA;2. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands;3. Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|