Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
REPRESENT-VISIBILITY REPRESENTATIONS OF BIPARTITE GRAPHS
Autore:
DEAN AM; HUTCHINSON JP;
Indirizzi:
MACALESTER COLL,DEPT MATH & COMP SCI ST PAUL MN 55105 MACALESTER COLL,DEPT MATH & COMP SCI ST PAUL MN 55105 SKIDMORE COLL,DEPT MATH & COMP SCI SARATOGA SPRINGS NY 12866
Titolo Testata:
Discrete applied mathematics
fascicolo: 1, volume: 75, anno: 1997,
pagine: 9 - 25
Fonte:
ISI
Lingua:
ENG
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
CompuMath Citation Index
Science Citation Index Expanded
Citazioni:
17
Recensione:
Indirizzi per estratti:
Citazione:
A.M. Dean e J.P. Hutchinson, "REPRESENT-VISIBILITY REPRESENTATIONS OF BIPARTITE GRAPHS", Discrete applied mathematics, 75(1), 1997, pp. 9-25

Abstract

The paper considers representations of bipartite graphs as rectangle-visibility graphs, i.e., graphs whose vertices are rectangles in the plane, with adjacency determined by horizontal and vertical visibility. It is shown that, for p less than or equal to q, K-p,K-q has a representation with no rectangles having collinear sides if and only if p less than or equal to 2 or p = 3 and q less than or equal to 4. More generally, it is shown that K-p,K-q is a rectangle-visibility graph if and only if p less than or equal to 4. Finally, it is shown that every bipartite rectangle-visibility graph on n greater than or equal to 4 vertices has at most 4n - 12 edges.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 18/09/20 alle ore 20:10:56