Edges and Switches, Tunnels and Bridges

Details Edges and Switches, Tunnels and Bridges Edges and Switches, Tunnels and Bridges

2007-05-03

arxiv.org/abs/0705.0413v1

Computational Geometry Theory & Applications 42(8): 790-802, 2009

Computer Science

Data Structures and Algorithms

15 pages, 11 figures. To appear in 10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007. This version inclu

Scientific paper

10.1016/j.comgeo.2008.05.005

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.

Affiliated with

Also associated with

No associations

Rating

Edges and Switches, Tunnels and Bridges does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Edges and Switches, Tunnels and Bridges, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Edges and Switches, Tunnels and Bridges will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-496952