2-Layer Right Angle Crossing Drawings |
| |
Authors: | Emilio Di Giacomo Walter Didimo Peter Eades Giuseppe Liotta |
| |
Affiliation: | 1. Università di Perugia, Perugia, Italy 2. University of Sydney, Sydney, Australia
|
| |
Abstract: | A 2-layer drawing represents a bipartite graph where each vertex is a point on one of two parallel lines, no two vertices on the same line are adjacent, and the edges are straight-line segments. In this paper we study 2-layer drawings where any two crossing edges meet at right angle. We characterize the graphs that admit this type of drawing, provide linear-time testing and embedding algorithms, and present a polynomial-time crossing minimization technique. Also, for a given graph G and a constant k, we prove that it is $\mathcal{NP}$ -complete to decide whether G contains a subgraph of at least k edges having a 2-layer drawing with right angle crossings. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|