Back to Search
Start Over
2-Layer Right Angle Crossing Drawings.
- Source :
-
Algorithmica . Apr2014, Vol. 68 Issue 4, p954-997. 44p. - Publication Year :
- 2014
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 68
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 94398412
- Full Text :
- https://doi.org/10.1007/s00453-012-9706-7