A 2-layer drawing represents a bipartite graph so that the vertices of each partition set are points of a distinct horizontal line (called a layer) and the edges are straight-line segments. In this paper we study 2-layer drawings where all edge crossings form right angles. We characterize which graphs 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 NP-complete to decide whether G contains a subgraph of at least k edges having a 2-layer drawing with right angle crossings.
2-Layer Right Angle Crossing Drawings
DI GIACOMO, Emilio;DIDIMO, WALTER;LIOTTA, Giuseppe
2011
Abstract
A 2-layer drawing represents a bipartite graph so that the vertices of each partition set are points of a distinct horizontal line (called a layer) and the edges are straight-line segments. In this paper we study 2-layer drawings where all edge crossings form right angles. We characterize which graphs 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 NP-complete to decide whether G contains a subgraph of at least k edges having a 2-layer drawing with right angle crossings.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
